Approximation schemes for minimum latency problems

Sanjeev Arora; George Karakostas

doi:10.1145/301250.301432

Approximation schemes for minimum latency problems

Sanjeev Arora, George Karakostas

Research output: Contribution to journal › Conference article › peer-review

35 Scopus citations

Abstract

The minimum latency problem, also known as traveling repairman problem, is a variant of the TSP 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 quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the nodes lie in R^d for some fixed d. The best polynomial time approximation algorithm due to Goemans and Kleinberg, computes a 3.59... approximation.

Original language	English (US)
Pages (from-to)	688-693
Number of pages	6
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/301250.301432
State	Published - 1999
Event	Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA Duration: May 1 1999 → May 4 1999

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/301250.301432

Cite this

@article{827d68a518754f36bda0e537436ec3b3,

title = "Approximation schemes for minimum latency problems",

abstract = "The minimum latency problem, also known as traveling repairman problem, is a variant of the TSP 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 quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the nodes lie in Rd for some fixed d. The best polynomial time approximation algorithm due to Goemans and Kleinberg, computes a 3.59... approximation.",

author = "Sanjeev Arora and George Karakostas",

year = "1999",

doi = "10.1145/301250.301432",

language = "English (US)",

pages = "688--693",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 ; Conference date: 01-05-1999 Through 04-05-1999",

}

TY - JOUR

T1 - Approximation schemes for minimum latency problems

AU - Arora, Sanjeev

AU - Karakostas, George

PY - 1999

Y1 - 1999

N2 - The minimum latency problem, also known as traveling repairman problem, is a variant of the TSP 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 quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the nodes lie in Rd for some fixed d. The best polynomial time approximation algorithm due to Goemans and Kleinberg, computes a 3.59... approximation.

AB - The minimum latency problem, also known as traveling repairman problem, is a variant of the TSP 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 quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the nodes lie in Rd for some fixed d. The best polynomial time approximation algorithm due to Goemans and Kleinberg, computes a 3.59... approximation.

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

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

U2 - 10.1145/301250.301432

DO - 10.1145/301250.301432

M3 - Conference article

AN - SCOPUS:0032629112

SN - 0734-9025

SP - 688

EP - 693

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99

Y2 - 1 May 1999 through 4 May 1999

ER -

Approximation schemes for minimum latency problems

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this