Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/70155
Title: Approximation algorithms for min-max path cover problems with service handling time
Authors: Xu, Z 
Liang, X
Keywords: Approximation algorithm
Inapproximability
Min-max vehicle routing
Path covers
Issue Date: 2009
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2009, v. 5878, p. 383-392 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
Abstract: This paper presents improved approximation algorithms and inapproximability results for min-max path cover problems with service handling time, which have wide applications in practice when the latest service completion time for customers is critical. We study three variants of this problem, where paths must start (i) from a given depot, (ii) from any depot of a given set, and (iii) from any vertex of the given graph, respectively. For these three variants, we are able to achieve approximation ratios of 3, (4 + ε), and (5 + ε), respectively, for any ε> 0. We have further shown that approximation ratios less than 4/3, 3/2, and 3/2 are impossible for them, respectively, unless NP = P.
Description: 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, USA, December 16-18, 2009
URI: http://hdl.handle.net/10397/70155
ISBN: 978-3-642-10630-9
978-3-642-10631-6
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/978-3-642-10631-6_40
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

3
Last Week
0
Last month
Citations as of Apr 14, 2018

Page view(s)

29
Last Week
5
Last month
Citations as of Apr 15, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.