The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Steiner Tree Approximation via Iterative Randomized Rounding
Open accessAbstract
The Steiner tree problem is one of the most fundamental NP -hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + ε < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
B., T. A. A. (1946) · The Mathematical Gazette · doi:10.1017/s0025557200071461 · Cited by 7,129
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
(2011) · SpringerReference · doi:10.1007/springerreference_57547 · Cited by 3,190
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,376
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · Combinatorica · doi:10.1007/bf02579273 · Cited by 2,011
An Introduction to the Theory of Numbers.
LeVeque, W. J., Niven, I., & Zuckerman, H. S. (1961) · The American Mathematical Monthly · doi:10.2307/2311171 · Cited by 1,907
Probability and computing: randomized algorithms and probabilistic analysis
Mitzenmacher, M., & Upfal, E. (2005) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,824
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Mitzenmacher, M., & Upfal, E. (2005) · Cambridge University Press eBooks · doi:10.1017/cbo9780511813603 · Cited by 1,733
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Arora, S. (1998) · Journal of the ACM · doi:10.1145/290179.290180 · Cited by 1,137
A General Approximation Technique for Constrained Forest Problems
Goemans, M. X., & Williamson, D. P. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793242618 · Cited by 884
Hwang, F. K., Richards, D., & Winter, P. (1992) · Cited by 855
Edmonds, J. (1967) · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · doi:10.6028/jres.071b.032 · Cited by 731
Vazirani, V. V. (2003) · Springer eBooks · doi:10.1007/978-3-662-04565-7 · Cited by 716
Dreyfus, S. E., & Wagner, R. A. (1971) · Networks · doi:10.1002/net.3230010302 · Cited by 696
Gilbert, E. N., & Pollak, H. O. (1968) · SIAM Journal on Applied Mathematics · doi:10.1137/0116001 · Cited by 690
On Steiner trees and minimum spanning trees in hypergraphs
Polzin, T., & Daneshmand, S. V. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(02)00185-2 · Cited by 622
Improved Steiner tree approximation in graphs
Robins, G., & Zelikovsky, A. (2000) · doi:10.5555/338219.338638 · Cited by 524
Tighter Bounds for Graph Steiner Tree Approximation
Robins, G., & Zelikovsky, A. (2005) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480101393155 · Cited by 327
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
(2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976465 · Cited by 288
New Approximation Algorithms for the Steiner Tree Problems
Karpinski, M., & Zelikovsky, A. (1997) · Journal of Combinatorial Optimization · doi:10.1023/a:1009758919736 · Cited by 192
Approximation via cost sharing
Gupta, A., Kumar, A., ́al, M. P., et al. (2007) · Journal of the ACM · doi:10.1145/1236457.1236458 · Cited by 84
A Faster Algorithm for the Steiner Tree Problem
Mölle, D., Richter, S., & Rossmanith, P. (2006) · Lecture notes in computer science · doi:10.1007/11672142_46 · Cited by 75
A partition-based relaxation for Steiner trees
Könemann, J., Pritchard, D., & Tan, K. (2009) · Mathematical Programming · doi:10.1007/s10107-009-0289-2 · Cited by 26
Hypergraphic LP Relaxations for Steiner Trees
Chakrabarty, D., Könemann, J., & Pritchard, D. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13036-6_29 · Cited by 22
New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem
Chakrabarty, D., Devanur, N. R., & Vazirani, V. V. (2008) · Springer eBooks · doi:10.1007/978-3-540-68891-4_24 · Cited by 15
Cited by
Reducing the CNOT count for Clifford+T circuits on NISQ architectures
Gheorghiu, V., Huang, J., Li, S. M., Mosca, M., & Mukhopadhyay, P. (2020) · arXiv · doi:10.48550/arxiv.2011.12191 · Cited by 31
Metadata
- Authors
- Byrka, J., Grandoni, F., Rothvoss, T., & Sanità, L.
- Venue
- Journal of the ACM
- Published
- 2013-02
- Volume
- 60
- Issue
- 1
- Pages
- 1-33
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1976584101
- Cited by
- 281
- References
- 26
- FWCI
- 20.89
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.