Article

Universal approximations for TSP, Steiner tree, and set cover

Authors:

Guevara Noubir,

Rajmohan Rajaraman,

Ravi SundaramAuthors Info & Claims

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Pages 386 - 395

https://doi.org/10.1145/1060590.1060649

Published: 22 May 2005 Publication History

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]

N. Alon and Y. Azar. On-line Steiner trees in the Euclidean plane. In Proceedings of the Eighth Annual ACM Symposium on Computational Geometry, pages 337--343, 1992.

Digital Library

[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.

Digital Library

[4]

Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke. Optimal oblivious routing in polynomial time. In Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing (STOC), pages 383--388, 2003.

Digital Library

[5]

Y. Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the Thirty-Seventh IEEE Symposium on Foundations of Computer Science (FOCS), pages 184--193, 1996.

Digital Library

[6]

Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proceedings of the Thirtieth ACM Symposium on Theory of Computing (STOC), pages 161--168, 1998.

Digital Library

[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.

Digital Library

[8]

A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, UK, 1998.

Digital Library

[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]

B. Dean, M. Goemans, and J. Vondrak. Approximating the stochastic knapsack problem: the benefit of adaptivity. In Proceedings of the Forty-Fifth IEEE Symposium on Foundations of Computer Science (FOCS), 2004.

Digital Library

[11]

J. Fakcheroenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing (STOC), pages 448--455, 2003.

Digital Library

[12]

A. Fiat and G. J. Woeginger, editors. Online Algorithms: The State of the Art. Springer, 1998.

Digital Library

[13]

M. R. Garey and D. S. Johnson. Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman, San Francisco, 1979.

Digital Library

[14]

A. Goel and D. Estrin. Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), pages 499--505, 2003.

Digital Library

[15]

A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the Forty-Fourth IEEE Symposium on Foundations of Computer Science (FOCS), 2003.

Digital Library

[16]

A. Gupta, M. Pal, R. Ravi, and A. Sinha. Boosted sampling: Approximation algorithms for stochastic optimization. In Proceedings of the Thirty-Sixth ACM Symposium on Theory of Computing (STOC), pages 417--426, 2004.

Digital Library

[17]

N. Immorlica, D. R. Karger, M. Minkoff, and V. S. Mirrokni. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04), pages 691--700, 2004.

Digital Library

[18]

D. R. Karger and M. Minkoff. Building steiner trees with incomplete global knowledge. In Proceedings of the Forty-First IEEE Symposium on Foundations of Computer Science (FOCS), pages 613--623, 2000.

Digital Library

[19]

R. R. Mettu and C. G. Plaxton. The online median problem. In Proceedings of the Forty-First IEEE Symposium on Foundations of Computer Science (FOCS), pages 339--348, 2000.

Digital Library

[20]

A. Meyerson. Online facility location. In Proceedings of the Forty-Second IEEE Symposium on Foundations of Computer Science (FOCS), pages 426--433, 2001.

Digital Library

[21]

M. Minkoff. Approximation Algorithms for Combinatorial Optimization Under Uncertainty. PhD thesis, M.I.T., Cambridge, MA, 2003.

Digital Library

[22]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA, 2000.

Digital Library

[23]

L. K. Platzman and I. J. J. Bartholdi. Spacefilling curves and the planar travelling salesman problem. Journal of the ACM (JACM), 36(4):719--737, October 1989.

Digital Library

[24]

C. G. Plaxton. Approximation algorithms for hierarchical location problems. In Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing (STOC), pages 40--49, 2003.

Digital Library

[25]

H. Racke. Minimizing congestion in general networks. In Proceedings of the Forty-Third IEEE Symposium on Foundations of Computer Science (FOCS), pages 43--52, 2002.

Digital Library

[26]

D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202--208, 1985.

Digital Library

[27]

L. G. Valiant and G. Brebner. Universal schemes for parallel communication. In Proceedings of the Thirteenth ACM Symposium on Theory of Computing (STOC), pages 263--277, 1981.

Digital Library

Cited By

Filtser A(2024)Scattering and Sparse Partitions, and Their ApplicationsACM Transactions on Algorithms10.1145/367256220:4(1-42)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3672562
Busch CChen DFiltser AHathcock DHershkowitz DRajaraman R(2023)One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00012(60-76)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00012
Erschler AMitrofanov I(2023)Spaces that can be ordered effectively: virtually free groups and hyperbolicityGeometriae Dedicata10.1007/s10711-023-00791-1217:4Online publication date: 30-May-2023
https://doi.org/10.1007/s10711-023-00791-1
Show More Cited By

Index Terms

Universal approximations for TSP, Steiner tree, and set cover
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Approximating the selected-internal Steiner tree

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph G=(V,E) with a cost function c:E->R^+ and two subsets R and R^' satisfying R^'@?R@?V, a selected-internal Steiner tree is a Steiner tree which contains (...
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

Given a weighted graph with some subsets of vertices called groups, the group Steiner tree problem is to find a minimum-weight subgraph which contains at least one vertex from each group. We give a randomized algorithm with a polylogarithmic ...
Improved approximations for buy-at-bulk and shallow-light $$k$$k-Steiner trees and $$(k,2)$$(k,2)-subgraph

In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light $$k$$k-Steiner tree problem (SL$$k$$kST), we are given an undirected graph $$G=(V,E)$$G=(V,E) with terminals $$T\subseteq ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

May 2005

778 pages

ISBN:1581139608

DOI:10.1145/1060590

General Chair:
Hal Gabow
University of Colorado
,
Program Chair:
Ronald Fagin
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC05

Sponsor:

STOC05: Symposium on Theory of Computing

May 22 - 24, 2005

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
1,021
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)5

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Filtser A(2024)Scattering and Sparse Partitions, and Their ApplicationsACM Transactions on Algorithms10.1145/367256220:4(1-42)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3672562
Busch CChen DFiltser AHathcock DHershkowitz DRajaraman R(2023)One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00012(60-76)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00012
Erschler AMitrofanov I(2023)Spaces that can be ordered effectively: virtually free groups and hyperbolicityGeometriae Dedicata10.1007/s10711-023-00791-1217:4Online publication date: 30-May-2023
https://doi.org/10.1007/s10711-023-00791-1
Czumaj AJiang SKrauthgamer RVesely PYang M(2022)Streaming Facility Location in High Dimension via Geometric Hashing2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00050(450-461)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00050
Rai SSharma GBusch CHerlihy M(2022)Load balanced distributed directoriesInformation and Computation10.1016/j.ic.2021.104700285(104700)Online publication date: May-2022
https://doi.org/10.1016/j.ic.2021.104700
Eades PMestre J(2020)An Optimal Lower Bound for Hierarchical Universal Solutions for TSP on the PlaneComputing and Combinatorics10.1007/978-3-030-58150-3_18(222-233)Online publication date: 27-Aug-2020
https://doi.org/10.1007/978-3-030-58150-3_18
Busch CHerlihy MPopovic MSharma G(2018)Time-communication impossibility results for distributed transactional memoryDistributed Computing10.1007/s00446-017-0318-y31:6(471-487)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00446-017-0318-y
Rai SSharma GBusch CHerlihy M(2018)Load Balanced Distributed DirectoriesStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-03232-6_15(221-238)Online publication date: 20-Oct-2018
https://doi.org/10.1007/978-3-030-03232-6_15
Christodoulou GSgouritsa AKlein P(2017)An improved upper bound for the universal TSP on the gridProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039750(1006-1021)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039750
Gupta ANagarajan VRavi R(2017)Approximation Algorithms for Optimal Decision Trees and Adaptive TSP ProblemsMathematics of Operations Research10.1287/moor.2016.083142:3(876-896)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1287/moor.2016.0831
Show More Cited By

View Options

Get Access

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