An Improved Approximation Algorithm for the s-t Path Movement Problem
This paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex to destination vertex . The best known algorithm for this problem is a 7-approximation algorithm developed by Berman, Demaine, and Zadimoghaddam in 2011. We refine t...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | บทความวารสาร |
| Language: | English |
| Published: |
Science Faculty of Chiang Mai University
2019
|
| Online Access: | http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7681 http://cmuir.cmu.ac.th/jspui/handle/6653943832/63855 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| Language: | English |
| id |
th-cmuir.6653943832-63855 |
|---|---|
| record_format |
dspace |
| spelling |
th-cmuir.6653943832-638552019-05-07T09:57:22Z An Improved Approximation Algorithm for the s-t Path Movement Problem Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenpho Sanpawat Kantabutra This paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex to destination vertex . 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 -approximation algorithm for any constant . 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 . 2019-05-07T09:57:22Z 2019-05-07T09:57:22Z 2017 บทความวารสาร 0125-2526 http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7681 http://cmuir.cmu.ac.th/jspui/handle/6653943832/63855 Eng Science Faculty of Chiang Mai University |
| institution |
Chiang Mai University |
| building |
Chiang Mai University Library |
| country |
Thailand |
| collection |
CMU Intellectual Repository |
| language |
English |
| description |
This paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex to destination vertex . 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 -approximation algorithm for any constant . 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 . |
| format |
บทความวารสาร |
| author |
Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenpho Sanpawat Kantabutra |
| spellingShingle |
Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenpho Sanpawat Kantabutra An Improved Approximation Algorithm for the s-t Path Movement Problem |
| author_facet |
Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenpho 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 |
| publisher |
Science Faculty of Chiang Mai University |
| publishDate |
2019 |
| url |
http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7681 http://cmuir.cmu.ac.th/jspui/handle/6653943832/63855 |
| _version_ |
1681425972941815808 |