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

Zhou Xu, Liang Xu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 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 languageEnglish
Title of host publicationAlgorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Pages383-392
Number of pages10
DOIs
Publication statusPublished - 1 Dec 2009
Event20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States
Duration: 16 Dec 200918 Dec 2009

Publication series

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

Conference

Conference20th International Symposium on Algorithms and Computation, ISAAC 2009
CountryUnited States
CityHonolulu, HI
Period16/12/0918/12/09

Keywords

  • Approximation algorithm
  • Inapproximability
  • Min-max vehicle routing
  • Path covers

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this