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...

Full description

Saved in:

Bibliographic Details
Main Authors:	Wattana Jindaluang, Jakarin Chawachat, Varin Chouvatut, Jittat Fakcharoenphol, Sanpawat Kantabutra
Format:	Journal
Published:	2018
Subjects:	Biochemistry, Genetics and Molecular Biology Chemistry Materials Science Mathematics Physics and Astronomy
Online Access:	https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/56835
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Chiang Mai University

id	th-cmuir.6653943832-56835
record_format	dspace
spelling	th-cmuir.6653943832-568352018-09-05T03:53:57Z An improved approximation algorithm for the s-t path movement problem Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenphol Sanpawat Kantabutra Biochemistry, Genetics and Molecular Biology Chemistry Materials Science Mathematics Physics and Astronomy © 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-09-05T03:30:51Z 2018-09-05T03:30:51Z 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/56835
institution	Chiang Mai University
building	Chiang Mai University Library
country	Thailand
collection	CMU Intellectual Repository
topic	Biochemistry, Genetics and Molecular Biology Chemistry Materials Science Mathematics Physics and Astronomy
spellingShingle	Biochemistry, Genetics and Molecular Biology Chemistry Materials Science Mathematics Physics and Astronomy 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/56835
_version_	1681424766244749312

An improved approximation algorithm for the s-t path movement problem

Similar Items