Approximation schemes for minimum latency problems

Sanjeev Arora, George Karakostas

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

The minimum latency problem, also known as the traveling repairman problem, is a variant of the traveling salesman problem in which the starting node of the tour is given and the goal is to minimize the sum of the arrival times at the other nodes. We present a quasi-polynomial time approximation scheme (QPTAS) for this problem when the instance is a weighted tree, when the nodes lie in ℝd for some fixed d, and for planar graphs. We also present a polynomial time constant factor approximation algorithm for the general metric case. The currently best polynomial time approximation algorithm for general metrics, due to Goemans and Kleinberg, computes a 3.59-approximation.

Original languageEnglish (US)
Pages (from-to)1317-1337
Number of pages21
JournalSIAM Journal on Computing
Volume32
Issue number5
DOIs
StatePublished - Aug 2003

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximation algorithms
  • Minimum latency tour
  • Quasi-polynomial approximation schemes
  • Randomized search ratio
  • Search ratio
  • Traveling repairman
  • Vehicle routing

Fingerprint

Dive into the research topics of 'Approximation schemes for minimum latency problems'. Together they form a unique fingerprint.

Cite this