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

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: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 2: Piotr Berman , Sridhar Hannenhalli , Marek Karpinski, 1.375-Approximation Algorithm for Sorting by Reversals, Proceedings of the 10th Annual European Symposium on Algorithms, p.200-210, September 17-21, 2002
• 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.
• 4: Markus Bläser , Bodo Siebert, Computing Cycle Covers without Short Cycles, Proceedings of the 9th Annual European Symposium on Algorithms, p.368-379, August 28-31, 2001
• 5: {C76} N. Christofides, Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem, Technical Report, GSIA, Carnegie-Mellon University, 1976.
• 6: Lars Engebretsen , Marek Karpinski, Approximation Hardness of TSP with Bounded Metrics, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.201-212, July 08-12, 2001
• 7: W. Fernandez de la Vega , M. Karpinski, On the approximation hardness of dense TSP and other path problems, Information Processing Letters, v.70 n.2, p.53-55, April 30, 1999 [doi>10.1016/S0020-0190(99)00048-4 ]
• 8: {H84} D. B. Hardvigsen, Extensions of Matching Theory, Ph. D. Thesis, Carnegie Mellon University, 1984.
• 9: {K72} R. M. Karp, Reducibility among Combinatorial Problems, in R. E. Miller and J. W. Thatcher (Eds.), Plenum, New York, 1972.
• 10: Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993
• 11: Luca Trevisan, When Hamming meets Euclid: the approximability of geometric TSP and MST (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.21-29, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258541]
• 12: Sundar Vishwanathan, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, Information Processing Letters, v.44 n.6, p.297-302, Dec. 28, 1992 [doi>10.1016/0020-0190(92)90103-3 ]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation
      G.1.6 Optimization
          Subjects: Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory