Universal approximations for TSP, Steiner tree, and set cover

ABSTRACT

We introduce a notion of universality in the context of optimization problems with partial information. Universality is a framework for dealing with uncertainty by guaranteeing a certain quality of goodness for all possible completions of the partial information set. Universal variants of optimization problems can be defined that are both natural and well-motivated. We consider universal versions of three classical problems: TSP, Steiner Tree and Set Cover.We present a polynomial-time algorithm to find a universal tour on a given metric space over n vertices such that for any subset of the vertices, the sub-tour induced by the subset is within O(log⁴ⁿ/log log n) of an optimal tour for the subset. Similarly, we show that given a metric space over n vertices and a root vertex, we can find a universal spanning tree such that for any subset of vertices containing the root, the sub-tree induced by the subset is within O(log⁴ⁿ/log log n) of an optimal Steiner tree for the subset. Our algorithms rely on a new notion of sparse partitions, that may be of independent interest. For the special case of doubling metrics, which includes both constant-dimensional Euclidean and growth-restricted metrics, our algorithms achieve an O(log n) upper bound. We complement our results for the universal Steiner tree problem with a lower bound of Ω(log n/log log n) that holds even for n vertices on the plane. We also show that a slight generalization of the universal Steiner Tree problem is coNP-hard and present nearly tight upper and lower bounds for a universal version of Set Cover.

REFERENCES

• 1: http://www.mathcs.emory.edu/~mic/interests.html.
• 2: 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]
• 3: B. Awerbuch and D. Peleg. Sparse partitions. In Proceedings of the Thirty-First IEEE Symposium on Foundations of Computer Science (FOCS), pages 503--513, 1990.
• 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: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 6: 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]
• 7: D. Bertsimas and M. Grigni. On the space-filling curve heuristic for the euclidean traveling salesman problem. Operations Research Letters, 8:241--244, October 1989.
• 8: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 9: J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer Systems and Sciences (JCSS), 18:143--154, 1979.
• 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: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 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: Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 15: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 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: 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
• 18: 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
• 19: R. R. Mettu , C. G. Plaxton, The online median problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.339, November 12-14, 2000
• 20: A. Meyerson, Online Facility Location, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.426, October 14-17, 2001
• 21: Maria Minkoff , David R. Karger, Approximation algorithms for combinatorial optimization under uncertainty, 2003
• 22: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 23: 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]
• 24: C. Greg Plaxton, Approximation algorithms for hierarchical location problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780549]
• 25: 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
• 26: 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]
• 27: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
Steiner tree, TSP, approximation algorithms, set cover, sparse partition, universal approximation