On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs
In a series of papers throughout the last decade, the approximation guarantee $c$ for the Steiner tree problem has been improved to the currently best known value of 1. 55 (Robins, Zelikovsky). Robins' and Zelikovsky's algorithm as well as most of its predecessors are greedy algorithms.
Apart from algorithmic improvements, there also has been substantial work on obtaining tight linear-programming relaxations for the Steiner tree problem. Many undirected and directed formulations have been proposed in the course of the last 25 years; their use, however, is to this point mostly restricted to the field of exact optimization. There are few examples of algorithms for the Steiner tree problem that make use of these LP relaxations. The best known such algorithm for general graphs is a 2-approximation (for the more general Steiner forest problem) due to Agrawal, Klein and Ravi. Their analysis is tight as the LP-relaxation used in their work is known to be weak: it has an IP/LP gap of approximately 2.
Most recent efforts to obtain algorithms for the Steiner tree problem that are based on LP-relaxations has focused on directed relaxations. In this thesis we present an undirected relaxation and show that the algorithm of Robins and Zelikovsky returns a Steiner tree whose cost is at most 1. 55 times its optimum solution value. In fact, we show that this algorithm can be viewed as a primal-dual algorithm.
The Steiner forest problem is a generalization of the Steiner tree problem. In the problem, instead of only one set of terminals, we are given more than one terminal set. An feasible Steiner forest is a forest that connects all terminals in the same terminal set for each terminal set. The goal is to find a minimum cost feasible Steiner forest. In this thesis, a new set of facet defining inequalities for the polyhedra of the Steiner forest is introduced.
School:University of Waterloo
School Location:Canada - Ontario
Source Type:Master's Thesis
Keywords:mathematics aproximation algorithms steiner tree forest partition inequalities
Date of Publication:01/01/2006