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:	Chemistry Materials Science Mathematics Agricultural and Biological Sciences
Online Access:	https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/46463
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Chiang Mai University

id	th-cmuir.6653943832-46463
record_format	dspace
spelling	th-cmuir.6653943832-464632018-04-25T07:30:53Z An improved approximation algorithm for the s-t path movement problem Wattana Jindaluang Jakarin Chawachat Varin Chouvatut Jittat Fakcharoenphol Sanpawat Kantabutra Chemistry Materials Science Mathematics Agricultural and Biological Sciences © 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-04-25T06:55:13Z 2018-04-25T06:55:13Z 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/46463
institution	Chiang Mai University
building	Chiang Mai University Library
country	Thailand
collection	CMU Intellectual Repository
topic	Chemistry Materials Science Mathematics Agricultural and Biological Sciences
spellingShingle	Chemistry Materials Science Mathematics Agricultural and Biological Sciences 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/46463
_version_	1681422879297634304

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

Similar Items