Article

8/7-approximation algorithm for (1,2)-TSP

Authors:

Piotr Berman,

Marek KarpinskiAuthors Info & Claims

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

Pages 641 - 648

Published: 22 January 2006 Publication History

Get Access

Abstract

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarly improving upon the best known approximation factor for that problem. The result depends on a new method of consecutive path cover improvements and on a new analysis of certain related color alternating paths. This method could be of independent interest.

References

[1]

{A96} S. Arora, Polynomial Time Approximation Schemes for Euclidean TSP and other Geometric Problems, Proc. 37th IEEE FOCS (1996), pp. 2--11.]]

Digital Library

Google Scholar

[2]

{BHK02} P. Berman, S. Hannenhalli and M. Karpinski, 1.375-Approximation Algorithm for Sorting by Reversals, Proc. 10th ESA (2002), LNCS 2461, Springer, 2002, pp. 200--210.]]

Digital Library

Google Scholar

[3]

{BR05} M. Bläser and L. Shankar Ram, An Improved Approximation for TSP with Distances One and Two, Proc. 15th FCT (2005), LNCS 3623, Springer, 2005, pp. 504--515.]]

Digital Library

Google Scholar

[4]

{BS01} M. Bläser and B. Seifert, Computing Cycle Covers without Short Cycles, Proc. 9th ESA (2001), LNCS 2161, Springer, 2001, pp. 368--379.]]

Digital Library

Google Scholar

[5]

{C76} N. Christofides, Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem, Technical Report, GSIA, Carnegie-Mellon University, 1976.]]

Google Scholar

[6]

{EK01} L. Engebretsen and M. Karpinski, Approximation Hardness of TSP with Bounded Metrics, Proc. 28th ICALP (2001), LNCS 2076, Springer, 2001, pp. 201--212; journal version to appear in JCSS.]]

Digital Library

Google Scholar

[7]

{FK99} W. Fernandez de la Vega and M. Karpinski, On the Approximation Hardness of Dense TSP and other Path Problems, Information Processing Letters 70 (1999), pp. 53--55.]]

Digital Library

Google Scholar

[8]

{H84} D. B. Hardvigsen, Extensions of Matching Theory, Ph. D. Thesis, Carnegie Mellon University, 1984.]]

Google Scholar

[9]

{K72} R. M. Karp, Reducibility among Combinatorial Problems, in R. E. Miller and J. W. Thatcher (Eds.), Plenum, New York, 1972.]]

Google Scholar

[10]

{PY93} C. H. Papadimitriou and M. Yannakakis, The Traveling Salesman Problem With Distances One and Two, Math. Oper. Res. 18 (1993), pp. 1--11.]]

Google Scholar

[11]

{T97} L. Trevisan, When Hamming Meets Euclid: The Approximability of Geometric TSP and MST, Proc. 29th ACM STOC (1997), pp. 21--29.]]

Digital Library

Google Scholar

[12]

{V92} S. Vishwanathan, An Approximation Algorithm for the Asymmetric Travelling Salesman Problem with Distances One and Two, Information Processing Letters 44 (1992), pp. 297--302.]]

Digital Library

Google Scholar

Cited By

View all

Bilò DFriedrich TLenzner PMelnichenko AScheideler CBerenbrink P(2019)Geometric Network Creation GamesThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323199(323-332)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323199
Shi FNeumann FWang JFriedrich TDoerr CArnold D(2019)Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340314(133-146)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340314
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
Show More Cited By

Index Terms

8/7-approximation algorithm for (1,2)-TSP
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming

Recommendations

Deterministic 7/8-approximation for the metric maximum TSP

We present the first 7/8-approximation algorithm for the maximum Traveling Salesman Problem (MAX-TSP) with triangle inequality. Our algorithm is deterministic. This improves over both the randomized algorithm of Hassin and Rubinstein [R. Hassin, S. ...
Reducing Path TSP to TSP

We present a black-box reduction from the path version of the traveling salesman problem (Path TSP) to the classical tour version (TSP). More precisely, given an $\alpha$-approximation algorithm for TSP, then, for any $\epsilon >0$, we obtain an $(\alpha+\...
Deterministic 7/8-Approximation for the Metric Maximum TSP
APPROX '08 / RANDOM '08: Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques

We present the first 7/8-approximation algorithm for the maximum traveling salesman problem with triangle inequality. Our algorithm is deterministic. This improves over both the randomized algorithm of Hassin and Rubinstein [2] with expected ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

January 2006

1261 pages

ISBN:0898716055

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
894
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bilò DFriedrich TLenzner PMelnichenko AScheideler CBerenbrink P(2019)Geometric Network Creation GamesThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323199(323-332)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323199
Shi FNeumann FWang JFriedrich TDoerr CArnold D(2019)Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340314(133-146)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340314
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
Weller MChateau AGiroudeau RKönig JPollet V(2018)On residual approximation in solution extension problemsJournal of Combinatorial Optimization10.5555/3287775.328781936:4(1195-1220)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3287775.3287819
Wörz S(2017)On global integer extrema of real-valued box-constrained multivariate quadratic functionsJournal of Combinatorial Optimization10.1007/s10878-017-0123-334:3(964-986)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s10878-017-0123-3
Svensson OTarnawski JVégh L(2016)Constant Factor Approximation for ATSP withźTwo Edge WeightsProceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization - Volume 968210.1007/978-3-319-33461-5_19(226-237)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-319-33461-5_19
Karpinski MLampis MSchmied R(2015)New inapproximability bounds for TSPJournal of Computer and System Sciences10.1016/j.jcss.2015.06.00381:8(1665-1677)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.jcss.2015.06.003
Lampis M(2014)Guest columnACM SIGACT News10.1145/2596583.259659945:1(48-65)Online publication date: 17-Mar-2014
https://dl.acm.org/doi/10.1145/2596583.2596599
Boyd SSitters RSter SStougie L(2014)The traveling salesman problem on cubic and subcubic graphsMathematical Programming: Series A and B10.1007/s10107-012-0620-1144:1-2(227-245)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1007/s10107-012-0620-1
Karpinski MSchmied R(2013)Improved inapproximability results for the shortest superstring and related problemsProceedings of the Nineteenth Computing: The Australasian Theory Symposium - Volume 14110.5555/2525519.2525523(27-36)Online publication date: 29-Jan-2013
https://dl.acm.org/doi/10.5555/2525519.2525523
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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Deterministic 7/8-approximation for the metric maximum TSP

Reducing Path TSP to TSP

Deterministic 7/8-Approximation for the Metric Maximum TSP

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations