A Primal Dual Algorithm On 2-Steiner Graphs
Abstract
The Steiner Tree Problem is a fundamental network design problem, where the goal is to connect a subset of terminals of a given network at minimum cost. A major open question regarding this problem, is proving that the integrality gap of a certain linear program relaxation, called the bidirected cut relaxation (BCR), is strictly smaller than 2.
In this thesis, we prove that (BCR) has integrality gap at most 5/3 for a subset of
instances, which we call 2-Steiner instances, via a primal-dual method.
Collections
Cite this version of the work
Matthew Buckley
(2018).
A Primal Dual Algorithm On 2-Steiner Graphs. UWSpace.
http://hdl.handle.net/10012/12949
Other formats