An Improved Approximation Algorithm for the s-t Path Movement Problem
Wattana Jindaluang [a], Jakarin Chawachat [b], Varin Chouvatut [b], Jittat Fakcharoenphol*[a] and Sanpawat Kantabutra [c]* Author for corresponding; e-mail address: jittat@gmail.com
Volume: Vol.44 No.1 (JANUARY 2017)
Research Article
DOI:
Received: 20 March 2015, Revised: -, Accepted: 3 July 2015, Published: -
Citation: Jindaluang W., Chawachat J., Chouvatut V., Fakcharoenphol J. and Kantabutra S., An Improved Approximation Algorithm for the s-t Path Movement Problem, Chiang Mai Journal of Science, 2017; 44(1): 279-286.
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 .