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: | , , , , |
---|---|
Format: | Journal |
Published: |
2017
|
Online Access: | https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/40989 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Chiang Mai University |
id |
th-cmuir.6653943832-40989 |
---|---|
record_format |
dspace |
spelling |
th-cmuir.6653943832-409892017-09-28T04:14:56Z An improved approximation algorithm for the s-t path movement problem Jindaluang W. Chawachat J. Chouvatut V. Fakcharoenphol J. Kantabutra S. © 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 + ϵ. 2017-09-28T04:14:56Z 2017-09-28T04:14:56Z 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/40989 |
institution |
Chiang Mai University |
building |
Chiang Mai University Library |
country |
Thailand |
collection |
CMU Intellectual Repository |
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 |
Jindaluang W. Chawachat J. Chouvatut V. Fakcharoenphol J. Kantabutra S. |
spellingShingle |
Jindaluang W. Chawachat J. Chouvatut V. Fakcharoenphol J. Kantabutra S. An improved approximation algorithm for the s-t path movement problem |
author_facet |
Jindaluang W. Chawachat J. Chouvatut V. Fakcharoenphol J. Kantabutra S. |
author_sort |
Jindaluang W. |
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 |
2017 |
url |
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/40989 |
_version_ |
1681421919120785408 |