Improved lower and upper bounds for universal TSP in planar metrics

ABSTRACT

A universal TSP tour of a metric space is a total ordering of the points of the space such that for any finite subset, the tour which visits these points in the given order is not too much longer than the optimal tour. There is a vast literature on the TSP problem, and universal TSP tours have been studied since the 1980's when Bartholdi and Platzman [29] introduced the spacefilling curve heuristic for the Euclidean TSP problem and conjectured that there exists a constant-competitive universal TSP tour based on this heuristic. Here, we settle this conjecture negatively by proving an Ω (6√log n/log log n) lower bound for universal TSP tours of the n × n grid; this is the first known example of a family of finite metrics with no constant-competitive universal tour.Generalizing from the n × n grid to arbitrary weighted planar graph metrics, and more generally H-minor-free metrics, we improve the best known upper bound for universal tours of such metrics from O(log⁴ n/ log log n) to O(log² n).

REFERENCES

• 1: Noga Alon , Yossi Azar, On-line Steiner trees in the Euclidean plane, Proceedings of the eighth annual symposium on Computational geometry, p.337-343, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142744]
• 2: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 3: Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , Andrzej Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.33-41, January 25-27, 1998, San Francisco, California, United States
• 4: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 5: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 6: D. Bertsimas and M. Grigni, Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem, Oper. Res. Lett., 8 (1989), pp. 241--244.
• 7: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 8: J. L. Carter and M. N. Wegman, Universal classes of hash functions, J. Comput. System Sci., 18 (1979), pp. 143--154.
• 9: N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, in Symposium on New Directions and Recent Results in Algorithms and Complexity, New York, NY, USA, 1976, Academic Press, p. 441.
• 10: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 11: Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
• 12: Developments from a June 1996 seminar on Online algorithms: the state of the art, January 1998
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: Michelangelo Grigni, Approximate TSP in Graphs with Forbidden Minors, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.869-877, July 09-15, 2000
• 15: M. Grigni , E. Koutsoupias , C. Papadimitriou, An approximation scheme for planar graph TSP, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.640, October 23-25, 1995
• 16: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 17: MohammadTaghi Hajiaghayi , Jeong Han Kim , Tom Leighton , Harald Räcke, Oblivious routing in directed graphs with random demands, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060619]
• 18: Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Räcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 19: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 20: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: Lujun Jia , Guolong Lin , Guevara Noubir , Rajmohan Rajaraman , Ravi Sundaram, Universal approximations for TSP, Steiner tree, and set cover, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060649]
• 22: D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
• 23: Philip N. Klein, A linear-time approximation scheme for planar weighted TSP, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.647-657, October 23-25, 2005 [doi>10.1109/SFCS.2005.7]
• 24: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 25: E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley and Sons, New York, 1985.
• 26: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 27: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 28: 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
• 29: Loren K. Platzman , John J. Bartholdi, III, Spacefilling curves and the planar travelling salesman problem, Journal of the ACM (JACM), v.36 n.4, p.719-737, Oct. 1989 [doi>10.1145/76359.76361]
• 30: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 31: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 32: Satish Rao , Andréa W. Richa, New approximation techniques for some ordering problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.211-218, January 25-27, 1998, San Francisco, California, United States
• 33: P. D. Seymour, Packing directed circuits fractionally, Combinatorica, 15 (1995), pp. 281--288.
• 34: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 35: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

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.6 Optimization
          Subjects: Integer programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Theory