Chiang Mai Journal of Science

An Improved Approximation Algorithm for the s-t Path Movement Problem

Paper Type	Contributed Paper
Title	An Improved Approximation Algorithm for the s-t Path Movement Problem
Author	Wattana Jindaluang [a], Jakarin Chawachat [b], Varin Chouvatut [b], Jittat Fakcharoenphol*[a] and Sanpawat Kantabutra [c]
Email	jittat@gmail.com
Abstract: 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 .
Start & End Page	279 - 286
Received Date	2015-03-20
Revised Date
Accepted Date	2015-07-03
Full Text	Download
Keyword	movement problems, approximation algorithm, graph algorithm
Volume	Vol.44 No.1 (JANUARY 2017)
DOI
Citation	[a] W.J., [b] J.C., [b] V.C., Fakcharoenphol*[a] J. and [c] S.K., An Improved Approximation Algorithm for the s-t Path Movement Problem, Chiang Mai Journal of Science, 2017; 44(1): 279-286.
View:858 Download:270