A partition-based relaxation for Steiner trees

DOI10.1007/s10107-009-0289-2zbMath1222.68413arXiv0712.3568OpenAlexW2121370879MaRDI QIDQ535014

Yong-Cai Geng, Sumit K. Garg

Publication date: 11 May 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0712.3568

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree, Chvátal-Gomory cuts for the Steiner tree problem, Stronger path‐based extended formulation for the Steiner tree problem, A linear programming based approach to the Steiner tree problem with a fixed number of terminals, Solving Steiner trees: Recent advances, challenges, and perspectives, On a partition LP relaxation for min-cost 2-node connected spanning subgraphs, New geometry-inspired relaxations and algorithms for the metric Steiner tree problem, Strong Steiner Tree Approximations in Practice, Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Survivable networks, linear programming relaxations and the parsimonious property
• A factor 2 approximation algorithm for the generalized Steiner network problem
• The Steiner tree problem on graphs: inapproximability results
• On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic
• On the spanning tree polyhedron
• The Steiner tree polytope and related polyhedra
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• New approximation algorithms for the Steiner tree problems
• Recent results on approximating the Steiner tree problem and its generalizations
• On Steiner trees and minimum spanning trees in hypergraphs
• An 11/6-approximation algorithm for the network Steiner problem
• A dual ascent approach for steiner tree problems on a directed graph
• New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• An integer linear programming approach to the steiner problem in graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Improved Approximations for the Steiner Tree Problem
• Thek-Steiner Ratio in Graphs
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• A catalog of steiner tree formulations
• Tighter Bounds for Graph Steiner Tree Approximation
• Optimum branchings
• Steiner Minimal Trees
• The steiner problem in graphs
• Blocking and anti-blocking pairs of polyhedra
• Combinatorial optimization. Theory and algorithms.
• Steiner trees and polyhedra
• A comparison of Steiner tree relaxations
• Improved algorithms for the Steiner problem in networks