Back to search

University of Waterloo

A Primal Dual Algorithm On 2-Steiner Graphs

Abstract

dc:description.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.

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

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Buckley, Matthew. A Primal Dual Algorithm On 2-Steiner Graphs. University of Waterloo, 2018. http://hdl.handle.net/10012/12949