New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
type: Item
instance of: scholarly article
title: New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
zbMATH Open document ID: 1231.90364
author: Deeparnab Chakrabarty
author: Nikhil R. Devanur
author: Vijay V. Vazirani
published in: Mathematical Programming. Series A. Series B
publication date: 2011-11-23T00:00:00Z
review text: The main focus of this paper is the bidirected cut relaxation for the metric Steiner tree problem. It is known that this problem is NP-complete. Hence, for practical applications, approximation algorithms are necessary. The best approximation algorithm for the Steiner problem is due to Robins and Zelikovsky. The authors prove a guarantee of \({1.55}\) for general graphs and also show that when restricted to the quasi-bipartite graphs, i.e., graphs that do not have edges connecting pair of Steiner nodes, the ratio is \(1.28\). However, it is not clear whether these results would imply an upper bound on the integrality gap of the bidirected cut relaxation. The authors of this paper restrict themselves to quasi-bipartite graphs. We note that the class of quasi-bipartite graphs is a non-trivial class for the bidirected cut relaxation. The best known upper bound on the integrality gap on such graphs was \(3/2\) (Rajagopalan and Vazirani). In Section 4 of this paper the authors describe the dual growing procedure (the EMBED algorithm) which helps to prove the following property about the bidirected cut relaxation in quasi-bipartite graphs: if the minimum spanning tree is the optimum Steiner tree, than the LP relaxation is exact. In Section 5 the authors show how to modify the EMBED algorithm and give a primal-dual algorithm achieving the upper bound of \(3/2\). This algorithm can be made to run in almost linear time. We note that Rizzi's algorithm runs in time \((O(n^{2}T(n,m)\log_{2}{c_{m}}))\) where \(T(n,m)\) is the time taken to compute the minimum spanning tree in an \(n\) nodes, \(m\) edges graph, while \(c_m\) is the maximum cost of an edge. Using a way of reducing costs, the authors describe in Section 6 a simple and fast algorithm which proves an upper bound of \(\sqrt{2}\) on the integrality gap for quasi-bipartite graphs. This algorithm runs in strongly polynomial time. In Section 7, using another way of reducing costs, the authors present a \(4/2\) factor appr…
reviewed by: Eleonor Ciurea
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5977603
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: graph algorithms
zbMATH Keywords: minimum Steiner tree
MaRDI profile type: Publication
full work available at URL: s10107-009-0299-0
OpenAlex ID: W2015423869
cites work: Q4542519
cites work: On a bidirected relaxation for the MULTIWAY CUT problem
cites work: Introduction to algorithms
cites work: The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
cites work: The Steiner tree problem. II: Properties and classes of facets
cites work: Q4893755
cites work: Optimum branchings
cites work: A catalog of steiner tree formulations
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: The Steiner tree problem
cites work: Q4318847
cites work: Equitable cost allocations via primal-dual-type algorithms
cites work: Rounding algorithms for a geometric embedding of minimum multiway cut
cites work: A partition-based relaxation for Steiner trees
cites work: On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic
cites work: Q4252355
cites work: Tighter Bounds for Graph Steiner Tree Approximation
cites work: Q4782696
cites work: A dual ascent approach for steiner tree problems on a directed graph
DOI: 10.1007/S10107-009-0299-0
description: scientific article; zbMATH DE number 5977603