On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs

[摘要] The Steiner tree problem is a classical, well-studied, $mathcal{NP}$-hard optimizationproblem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ ofterminals, andnon-negative costs $c_e$ for all edges $e$ in $E$. A feasible Steiner tree for a given instance is a tree $T$ in $G$ that spans all terminals in $R$. Thegoal is to compute a feasible Steiner tree of smallest cost. In this thesis wewill focus onapproximation algorithms for this problem: a$c$-approximation algorithm is an algorithm that returns a tree of cost at most $c$ times that of an optimum solution for any given input instance.

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 predecessorsare greedy algorithms.

Apart from algorithmic improvements, there also has been substantial workon obtaining tight linear-programming relaxations for the Steiner tree problem.Many undirected and directed formulations have been proposed in the course ofthe last 25 years; their use, however, is to this point mostly restricted to thefield of exactoptimization. There are few examples of algorithms for theSteiner tree problem that make use of these LP relaxations. The best known suchalgorithm for general graphs is a 2-approximation (for the more general Steinerforest problem) due to Agrawal, Klein and Ravi. Their analysis istight 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 thatare based on LP-relaxations has focused on directedrelaxations. In this thesis wepresent an undirected relaxation and show that the algorithm of Robins and Zelikovsky returns a Steinertree whose cost is at most 1.55 times its optimumsolution value. In fact, we show that this algorithm can be viewed as aprimal-dualalgorithm.

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 defininginequalities for the polyhedra of the Steiner forest is introduced.

[发布机构] University of Waterloo

[效力级别] Aproximation Algorithms

[关键词] Mathematics;Aproximation Algorithms;Steiner tree;Steiner forest;partition inequalities