A partition-based relaxation for Steiner trees

DOI10.1007/S10107-009-0289-2zbMATH Open1222.68413arXiv0712.3568OpenAlexW2121370879MaRDI QIDQ535014FDOQ535014

Yong-Cai Geng, Sumit K. Garg

Publication date: 11 May 2011

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

Abstract: The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G=(V,E), a set of terminals R, and non-negative costs c_e for all edges e in E. Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The nodes V R are called Steiner nodes. The best approximation algorithm known for the Steiner tree problem is due to Robins and Zelikovsky (SIAM J. Discrete Math, 2005); their greedy algorithm achieves a performance guarantee of 1+(ln 3)/2 ~ 1.55. The best known linear (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math. Programming, 1993) and achieves an approximation ratio of 2-2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky's algorithm has a natural primal-dual interpretation with respect to a novel partition-based linear programming relaxation. We also exhibit surprising connections between the new formulation and existing LPs and we show that the new LP is stronger than the bidirected cut formulation. An instance is b-quasi-bipartite if each connected component of G R has at most b vertices. We show that Robins' and Zelikovsky's algorithm has an approximation ratio better than 1+(ln 3)/2 for such instances, and we prove that the integrality gap of our LP is between 8/7 and (2b+1)/(b+1).

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

Recommendations

• An improved LP-based approximation for Steiner tree
• Steiner tree approximation via iterative randomized rounding
• scientific article; zbMATH DE number 2044939
• Tighter Bounds for Graph Steiner Tree Approximation
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• scientific article; zbMATH DE number 2038710
• New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
• Steiner trees in uniformly quasi-bipartite graphs.
• Hypergraphic LP relaxations for Steiner trees

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

This page was built for publication: A partition-based relaxation for Steiner trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q535014)