Iterative Rounding Approximation Algorithms in Network Design

iterative rounding;approximation algorithms;network design;degree bounded;prize collecting;fractional tokens;Combinatorics and Optimization

Shea, Marcus

University of Waterloo

关键词: iterative rounding;    approximation algorithms;    network design;    degree bounded;    prize collecting;    fractional tokens;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/5239/1/Shea_Marcus.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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.