On the Integrality Gap of the Prize-Collecting Steiner Forest LP
From MaRDI portal
Publication:5002620
DOI10.4230/LIPIcs.APPROX-RANDOM.2017.17zbMath1467.90082arXiv1706.06565OpenAlexW2643346538MaRDI QIDQ5002620
R. Ravi, Chaitanya Swamy, Jens Vygen, Kanstantsin Pashkovich, Neil Olver, Jochen Könemann
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1706.06565
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Cites Work
- A unified approach to approximating partial covering problems
- A note on the prize collecting traveling salesman problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- The Steiner tree problem on graphs: inapproximability results
- A constant-factor approximation algorithm for the \(k\)-MST problem
- Black-box reductions for cost-sharing mechanism design
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Prize-Collecting Steiner Networks via Iterative Rounding
- Saving an epsilon
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Reducibility among Combinatorial Problems
- Steiner Tree Approximation via Iterative Randomized Rounding
- Matroids and integrality gaps for hypergraphic steiner tree relaxations
This page was built for publication: On the Integrality Gap of the Prize-Collecting Steiner Forest LP
