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
Issue Date: 2009
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2009, v. 5878, p. 383-392
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.
Keywords: Approximation algorithm
Inapproximability
Min-max vehicle routing
Path covers
Publisher: Springer
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
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
Description: 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, USA, December 16-18, 2009
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

5
Last Week
0
Last month
Citations as of Aug 18, 2020

Page view(s)

89
Last Week
5
Last month
Citations as of Sep 15, 2020

Google ScholarTM

Check

Altmetric


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