An improved approximation algorithm for the s-t path movement problem
© 2017, Chiang Mai University. All rights reserved. This paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex s to destination vertex t. The best known algorithm for this problem is a 7-approximation algorithm developed by Ber...
Saved in:
| Main Authors: | , , , , |
|---|---|
| 格式: | 雜誌 |
| 出版: |
2018
|
| 主題: | |
| 在線閱讀: | https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/46463 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Chiang Mai University |
| id |
th-cmuir.6653943832-46463 |
|---|---|
| record_format |
dspace |
| spelling |
th-cmuir.6653943832-464632018-04-25T07:30:53Z An improved approximation algorithm for the s-t path movement problem Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenphol Sanpawat Kantabutra Chemistry Materials Science Mathematics Agricultural and Biological Sciences © 2017, Chiang Mai University. All rights reserved. This paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex s to destination vertex t. The best known algorithm for this problem is a 7-approximation algorithm developed by Berman, Demaine, and Zadimoghaddam in 2011. We refine the analysis of Berman et. al. to obtain an (3 + ϵ)-approximation algorithm for any constant ϵ > 0. This problem is a subroutine used by Berman et. al. for finding a solution to the connectivity movement problem. Using our improved algorithm as a subroutine, the approximation ratio for the connectivity movement problem improves from 136 to 104 + ϵ. 2018-04-25T06:55:13Z 2018-04-25T06:55:13Z 2017-01-01 Journal 01252526 2-s2.0-85010824713 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/46463 |
| institution |
Chiang Mai University |
| building |
Chiang Mai University Library |
| country |
Thailand |
| collection |
CMU Intellectual Repository |
| topic |
Chemistry Materials Science Mathematics Agricultural and Biological Sciences |
| spellingShingle |
Chemistry Materials Science Mathematics Agricultural and Biological Sciences Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenphol Sanpawat Kantabutra An improved approximation algorithm for the s-t path movement problem |
| description |
© 2017, Chiang Mai University. All rights reserved. This paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex s to destination vertex t. The best known algorithm for this problem is a 7-approximation algorithm developed by Berman, Demaine, and Zadimoghaddam in 2011. We refine the analysis of Berman et. al. to obtain an (3 + ϵ)-approximation algorithm for any constant ϵ > 0. This problem is a subroutine used by Berman et. al. for finding a solution to the connectivity movement problem. Using our improved algorithm as a subroutine, the approximation ratio for the connectivity movement problem improves from 136 to 104 + ϵ. |
| format |
Journal |
| author |
Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenphol Sanpawat Kantabutra |
| author_facet |
Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenphol Sanpawat Kantabutra |
| author_sort |
Wattana Jindaluang |
| title |
An improved approximation algorithm for the s-t path movement problem |
| title_short |
An improved approximation algorithm for the s-t path movement problem |
| title_full |
An improved approximation algorithm for the s-t path movement problem |
| title_fullStr |
An improved approximation algorithm for the s-t path movement problem |
| title_full_unstemmed |
An improved approximation algorithm for the s-t path movement problem |
| title_sort |
improved approximation algorithm for the s-t path movement problem |
| publishDate |
2018 |
| url |
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/46463 |
| _version_ |
1681422879297634304 |