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.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5239 |
| Date | 05 1900 |
| Creators | Shea, Marcus |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0012 seconds