The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
An improved LP-based approximation for steiner tree
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 the current best 1.55 [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directed-component cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+ε<1.39 approximation for Steiner tree. As a byproduct of our analysis, we show that the integrality gap of our LP is at most $1.55$, hence answering to the mentioned open question. This might have consequences for a number of related problems.
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
(1979) · Cited by 43,841
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
(2011) · SpringerReference · doi:10.1007/springerreference_57547 · Cited by 3,190
(2003) · Selected Papers of Alan J Hoffman · doi:10.1142/9789812796936_others05 · Cited by 2,465
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
(2006) · Algorithms and Combinatorics 21 · doi:10.1007/3-540-29297-7 · Cited by 1,156
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
The Rectilinear Steiner Tree Problem is $NP$-Complete
Garey, M. R., & Johnson, D. S. (1977) · SIAM Journal on Applied Mathematics · doi:10.1137/0132071 · Cited by 1,124
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
Wiley‐Interscience Series in Discrete Mathematics and Optimization
(2000) · Random Graphs · doi:10.1002/9781118032718.scard · Cited by 725
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
Combinatorial optimization: Theory and algorithms
(2001) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(01)90023-9 · Cited by 600
(2005) · Embedding Problems in Symplectic Geometry · doi:10.1515/9783110199697.107 · Cited by 461
Tighter Bounds for Graph Steiner Tree Approximation
Robins, G., & Zelikovsky, A. (2005) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480101393155 · Cited by 327
Korte, B., & Vygen, J. (2002) · Algorithms and Combinatorics · doi:10.1007/978-3-662-21711-5_16 · Cited by 273
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 factor 2 approximation algorithm for the generalized Steiner network problem
Jain, K. K. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743495 · Cited by 76
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
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
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
A comprehensive survey of Network Function Virtualization
Yi, B., Wang, X., Li, K., Das, S. K., & Huang, M. (2018) · Computer Networks · doi:10.1016/j.comnet.2018.01.021 · Cited by 534
Quantum circuit optimizations for NISQ architectures
Nash, B., Gheorghiu, V., & Mosca, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab79b1 · Cited by 139
CNOT circuit extraction for topologically-constrained quantum memories
Kissinger, A., & de Griend, A. M.-V. (2019) · arXiv · doi:10.48550/arxiv.1904.00633 · Cited by 60
NODLINK: An Online System for Fine-Grained APT Attack Detection and Investigation
Li, S., Dong, F., Xiao, X., Wang, H., Shao, F., Chen, J., Guo, Y., Chen, X., & Li, D. (2024) · Proceedings 2024 Network and Distributed System Security Symposium · doi:10.14722/ndss.2024.23204 · Cited by 45
Metadata
- Authors
- Byrka, J., Grandoni, F., Rothvoß, T., & Sanità, L.
- Venue
- Proceedings of the forty-second ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2010-06-05
- Pages
- 583-592
- OpenAlex
- W1991055327
- Cited by
- 296
- References
- 25
- FWCI
- 39.85
- Type
- conference paper
- 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.