Abstract
dc:description.abstractThe 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.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Buckley, Matthew
- Advisor dc:contributor.advisor
-
- Sanità, Laura
Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/12949