Approximation algorithms for min-max path cover problems with service handling time

Zhou Xu; Liang Xu

doi:10.1007/978-3-642-10631-6_40

Approximation algorithms for min-max path cover problems with service handling time

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

6 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Pages	383-392
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-10631-6_40
Publication status	Published - 1 Dec 2009
Event	20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States Duration: 16 Dec 2009 → 18 Dec 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5878 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Symposium on Algorithms and Computation, ISAAC 2009
Country/Territory	United States
City	Honolulu, HI
Period	16/12/09 → 18/12/09

Keywords

Approximation algorithm
Inapproximability
Min-max vehicle routing
Path covers

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1007/978-3-642-10631-6_40

Cite this

Xu, Z., & Xu, L. (2009). Approximation algorithms for min-max path cover problems with service handling time. In Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings (pp. 383-392). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS). https://doi.org/10.1007/978-3-642-10631-6_40

@inproceedings{403b96f4a4d04ce6a19e3b6fb4f91cc6,

title = "Approximation algorithms for min-max path cover problems with service handling time",

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",

author = "Zhou Xu and Liang Xu",

year = "2009",

month = dec,

day = "1",

doi = "10.1007/978-3-642-10631-6_40",

language = "English",

isbn = "3642106307",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "383--392",

booktitle = "Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings",

note = "20th International Symposium on Algorithms and Computation, ISAAC 2009 ; Conference date: 16-12-2009 Through 18-12-2009",

}

Xu, Z & Xu, L 2009, Approximation algorithms for min-max path cover problems with service handling time. in Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5878 LNCS, pp. 383-392, 20th International Symposium on Algorithms and Computation, ISAAC 2009, Honolulu, HI, United States, 16/12/09. https://doi.org/10.1007/978-3-642-10631-6_40

Approximation algorithms for min-max path cover problems with service handling time. / Xu, Zhou; Xu, Liang.
Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. p. 383-392 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Approximation algorithms for min-max path cover problems with service handling time

AU - Xu, Zhou

AU - Xu, Liang

PY - 2009/12/1

Y1 - 2009/12/1

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

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

KW - Approximation algorithm

KW - Inapproximability

KW - Min-max vehicle routing

KW - Path covers

UR - http://www.scopus.com/inward/record.url?scp=75649151378&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10631-6_40

DO - 10.1007/978-3-642-10631-6_40

M3 - Conference article published in proceeding or book

SN - 3642106307

SN - 9783642106309

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 383

EP - 392

BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings

T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009

Y2 - 16 December 2009 through 18 December 2009

ER -

Xu Z, Xu L. Approximation algorithms for min-max path cover problems with service handling time. In Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. p. 383-392. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-10631-6_40

Approximation algorithms for min-max path cover problems with service handling time

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this