More Web Proxy on the site http://driver.im/

research-article

An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem

Authors:

Arash Asadpour,

Michel X. Goemans,

Aleksander Mądry,

Shayan Oveis Gharan,

Amin SaberiAuthors Info & Claims

SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

Pages 379 - 389

Published: 17 January 2010 Publication History

Abstract

We consider the Asymmetric Traveling Salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O(log n/ log log n) of the optimum with high probability.

References

[1]

D. J. Aldous. A random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal on Discrete Mathematics, 3(4):450--465, 1990.

Digital Library

[2]

A. Asadpour and A. Saberi. Maximum entropy selection: a randomized rounding method. submitted.

[3]

M. Bläser. A new approximation algorithm for the asymmetric TSP with traingle inequality. In ACM-SIAM Symposium on Discrete Algorithms, pages 638--645, 2002.

Digital Library

[4]

B. Bollobas. Modern Graph Theory. Springer, 2002.

[5]

A. Broder. Generating random spanning trees. In 30th Annual Symposium on Foundations of Computer Science, pages 442--447, 1989.

Digital Library

[6]

M. Charikar, M. Goemans, and H. Karloff. On the integrality ratio for the asymmetric traveling salesman problem. Mathematics of Operations Research, 31:245--252, 2006.

Digital Library

[7]

C. Chekuri and J. Vondrak. Randomized pipage rounding for matroid polytopes and applications, 2009. http://arxiv.org/abs/0909.4348v1.

[8]

N. Christofides. Worst case analysis of a new heuristic for the traveling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.

[9]

C. J. Colbourn, W. J. Myrvold, and E. Neufeld. Two algorithms for unranking arborescences. Journal of Algorithms, 20(2):268--281, 1996.

Digital Library

[10]

J. Edmonds. Matroids and the greedy algorithm. Mathematical Programming, pages 127--136, 1971.

[11]

U. Feige and M. Singh. Improved approximation ratios for traveling salesman tours and paths in directed graphs. In 10th International Workshop, APPROX, pages 104--118, 2007.

Digital Library

[12]

A. M. Frieze, G. Galbiati, and F. Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12:23--39, 1982.

[13]

A. Ghosh, S. Boyd, and A. Saberi. Minimizing effective resistance of a graph. SIAM Rev., 50(1):37--66, 2008.

Digital Library

[14]

M. X. Goemans. Minimum bounded degree spanning trees. In 47th Annual Symposium on Foundations of Computer Science, pages 273--282, 2006.

Digital Library

[15]

A. Guenoche. Random spanning tree. Journal of Algorithms, 4:214--220, 1983.

[16]

N. S. H. Kaplan, M. Lewenstein and M. Sviridenko. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM, pages 602--626, 2005.

Digital Library

[17]

M. Held and R. Karp. The traveling salesman problem and minimum spanning trees. Operations Research, 18:1138--1162, 1970.

[18]

D. R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In 4th annual ACM-SIAM Symposium on Discrete algorithms, pages 21--30, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics.

Digital Library

[19]

J. Kelner and A. Madry. Faster generation of random spanning trees. In 50th Annual Symposium on Foundations of Computer Science, 2009.

Digital Library

[20]

V. G. Kulkarni. Generating random combinatorial objects. Journal of Algorithms, 11:185--207, 1990.

Digital Library

[21]

R. Lyons and Y. Peres. Probability on Trees and Networks. 2009. In preparation. Current version available at http://mypage.iu.edu/~rdlyons/.

[22]

A. Nemirovski. Lectures on modern convex optimization, 2005.

[23]

A. Panconesi and A. Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput., 26:350--368, 1997.

Digital Library

[24]

A. Schrijver. Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 2003.

[25]

D. B. Wilson. Generating random spanning trees more quickly than the cover time. In 28th Annual ACM Symposium on the Theory of Computing, pages 296--303. ACM, 1996.

Digital Library

[26]

R. Zenklusen, July 2009. Personal communication.

Cited By

An HKleinberg RShmoys D(2021)Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman ProblemACM Transactions on Algorithms10.1145/347853717:4(1-12)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3478537
Nägele MZenklusen RChan T(2019)A new dynamic programming approach for spanning trees with chain constraints and beyondProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310529(1550-1569)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310529
Bansal NCharikar MCohen E(2019)On a generalization of iterated and randomized roundingProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316313(1125-1135)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316313
Show More Cited By

An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem

Recommendations

An Olog n/log log n-Approximation Algorithm for the Asymmetric Traveling Salesman Problem

We present a randomized O log n /log log n -approximation algorithm for the asymmetric traveling salesman problem ATSP. This provides the first asymptotic improvement over the long-standing Îï log n -approximation bound stemming from the work of ...
An O(log n log log n) space algorithm for undirected st-connectivity
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

We present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam [6] and uses the universal exploration sequences for trees constructed by Koucký [13]. Our ...
Fully dynamic connectivity in O(log n(log log n)²) amortized expected time
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O(log n(log log n)²) amortized expected update time and O(log n/log log log n) query time, which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

January 2010

1690 pages

ISBN:9780898716986

Program Chair:
Moses Charikar
Princeton University

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 17 January 2010

Check for updates

Qualifiers

Research-article

Acceptance Rates

SODA '10 Paper Acceptance Rate 135 of 445 submissions, 30%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
441
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

An HKleinberg RShmoys D(2021)Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman ProblemACM Transactions on Algorithms10.1145/347853717:4(1-12)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3478537
Nägele MZenklusen RChan T(2019)A new dynamic programming approach for spanning trees with chain constraints and beyondProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310529(1550-1569)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310529
Bansal NCharikar MCohen E(2019)On a generalization of iterated and randomized roundingProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316313(1125-1135)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316313
Linhares ASwamy C(2018)Approximating min-cost chain-constrained spanning treesMathematical Programming: Series A and B10.5555/3288898.3288947172:1-2(17-34)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288947
Gottschalk CVygen J(2018)Better s---t-tours by Gao treesMathematical Programming: Series A and B10.5555/3288898.3288943172:1-2(191-207)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288943
Svensson OTarnawski JVégh L(2018)Constant factor approximation for ATSP with two edge weightsMathematical Programming: Series A and B10.5555/3288898.3288940172:1-2(371-397)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288940
Schild ADiakonikolas IKempe DHenzinger M(2018)An almost-linear time algorithm for uniform random spanning tree generationProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188852(214-227)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188852
Svensson OTarnawski JVégh LDiakonikolas IKempe DHenzinger M(2018)A constant-factor approximation algorithm for the asymmetric traveling salesman problemProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188824(204-213)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188824
Olver NZenklusen R(2018)Chain-constrained spanning treesMathematical Programming: Series A and B10.1007/s10107-017-1126-7167:2(293-314)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10107-017-1126-7
Chekuri CQuanrud KKlein P(2017)Near-linear time approximation schemes for some implicit fractional packing problemsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039737(801-820)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039737
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents