New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
From MaRDI portal
Publication:647390
DOI10.1007/S10107-009-0299-0zbMath1231.90364OpenAlexW2015423869MaRDI QIDQ647390
Vijay V. Vazirani, Deeparnab Chakrabarty, Nikhil R. Devanur
Publication date: 23 November 2011
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-009-0299-0
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints ⋮ On the Price of Stability of Undirected Multicast Games ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ A partition-based relaxation for Steiner trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A partition-based relaxation for Steiner trees
- On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic
- The Steiner tree problem
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- The Steiner tree problem. II: Properties and classes of facets
- On a bidirected relaxation for the MULTIWAY CUT problem
- Rounding algorithms for a geometric embedding of minimum multiway cut
- A dual ascent approach for steiner tree problems on a directed graph
- Equitable cost allocations via primal-dual-type algorithms
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A catalog of steiner tree formulations
- Tighter Bounds for Graph Steiner Tree Approximation
- Optimum branchings
This page was built for publication: New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
