Return to search

Iterative Rounding Approximation Algorithms in Network Design

Iterative rounding has been an increasingly popular approach to solving network design optimization problems ever since Jain introduced the concept in his revolutionary 2-approximation for the Survivable Network Design Problem (SNDP). This paper looks at several important iterative rounding approximation algorithms and makes improvements to some of their proofs. We generalize a matrix restatement of Nagarajan et al.'s token argument, which we can use to simplify the proofs of Jain's 2-approximation for SNDP and Fleischer et al.'s 2-approximation for the Element Connectivity (ELC) problem. Lau et al. show how one can construct a (2,2B + 3)-approximation for the degree bounded ELC problem, and this thesis provides the proof. We provide some structural results for basic feasible solutions of the Prize-Collecting Steiner Tree problem, and introduce a new problem that arises, which we call the Prize-Collecting Generalized Steiner Tree problem.

Identiferoai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5239
Date05 1900
CreatorsShea, Marcus
Source SetsUniversity of Waterloo Electronic Theses Repository
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0018 seconds