Approximation Algorithms for Network Connectivity Problems

FieldValue
dc.contributor.authorCameron, Amy
dc.date.accessioned2012-04-18T16:11:29Z
dc.date.available2012-04-18T16:11:29Z
dc.date.created2012
dc.date.issued2012
dc.identifier.urihttp://hdl.handle.net/10393/22734
dc.identifier.urihttp://dx.doi.org/10.20381/ruor-5633
dc.description.abstractIn this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.
dc.language.isoen
dc.publisherUniversité d'Ottawa / University of Ottawa
dc.subjectnetwork design
dc.subjectapproximation algorithms
dc.subjectintegrality gap
dc.subjectsurvivable network design problem
dc.subjectedge-connected
dc.subjectvertex-connected
dc.subjectlinear programming
dc.subjectapproximation guarantee
dc.subjectupper bound
dc.titleApproximation Algorithms for Network Connectivity Problems
dc.typeThesis
dc.faculty.departmentMathématiques et statistique / Mathematics and Statistics
dc.contributor.supervisorBoyd, Sylvia
dc.embargo.termsimmediate
dc.degree.namePhD
dc.degree.leveldoctorate
dc.degree.disciplineSciences / Science
thesis.degree.namePhD
thesis.degree.levelDoctoral
thesis.degree.disciplineSciences / Science
uottawa.departmentMathématiques et statistique / Mathematics and Statistics
CollectionThèses, 2011 - // Theses, 2011 -

Files