2026-09-18T19:13:33Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/46738 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Chekuri, Chandra S. Chekuri, Chandra S. Godfrey, Philip B. Har-Peled, Sariel Vondrak, Jan Ene, Alina 2014-01-16T18:00:47Z 2014-01-16T18:00:47Z 2013-12 2014-01-16T18:00:47Z 2013-12 In this thesis, we consider combinatorial optimization problems involving submodular functions and graphs. The problems we study are NP-hard and therefore, assuming that P =/= NP, there do not exist polynomial-time algorithms that always output an optimal solution. In order to cope with the intractability of these problems, we focus on algorithms that construct approximate solutions: An approximation algorithm is a polynomial-time algorithm that, for any instance of the problem, it outputs a solution whose value is within a multiplicative factor p of the value of the optimal solution for the instance. The quantity p is the approximation ratio of the algorithm and we aim to achieve the smallest ratio possible. Our focus in this thesis is on designing approximation algorithms for several combinatorial optimization problems. In the first part of this thesis, we study a class of constrained submodular minimization problems. We introduce a model that captures allocation problems with submodular costs and we give a generic approach for designing approximation algorithms for problems in this model. Our model captures several problems of interest, such as non-metric facility location, multiway cut problems in graphs and hypergraphs, uniform metric labeling and its generalization to hub location. Using a convex relaxation and rounding strategy, we achieve good approximation guarantees for several problems in this model. In particular, we match or improve the known approximation ratios for several problems in a unified fashion. In the second part of this thesis, we study muticommodity flow problems in both undirected and directed graphs and we make several contributions towards understanding the gap between fractional and integral multicommodity flows. We give a poly-logarithmic approximation with constant congestion for the node-disjoint paths problem and we show a poly-logarithmic upper bound on the gap between the maximum fractional and integral throughput flows in node-capacitated undirected graphs. Prior to our work, the best guarantees were only polynomial. In the process, we prove a conjecture of Chekuri, Khanna, and Shepherd on the connection between the treewidth of the graph and the existence of a good routing structure. Additionally, we initiate the study of integral throughput flow problems in directed graphs with symmetric demand pairs. We obtain a poly-logarithmic approximation with constant congestion for the all-or-nothing flow problem. In the third part of this thesis, we study several network design problems. The input to these problems is a graph with costs on the edges or the nodes and the output is a minimum cost subgraph that meets certain connectivity requirements. We study several network design problems in planar graphs, including the prize-collecting Steiner tree and forest and the survivable network design problem with node costs. We show that the special structure of planar graphs --- and more generally, bounded genus and minor-free graphs --- leads to algorithms whose approximation guarantees are a significant improvement over what can be achieved for general graphs. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-08-28T14:23:37Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 3 Ene_Alina.zip: 312571 bytes, checksum: 1fa2254fa8ecf09b349dca33c7a97323 (MD5) Ene_Alina.pdf: 1145670 bytes, checksum: 2b10d359171ec20887b223a0437f4684 (MD5) Ene_Alina.pdf: 1145670 bytes, checksum: 2b10d359171ec20887b223a0437f4684 (MD5) Made available in DSpace on 2014-01-16T18:00:47Z (GMT). No. of bitstreams: 3 Alina_Ene.pdf: 1145670 bytes, checksum: 2b10d359171ec20887b223a0437f4684 (MD5) Ene_Alina.zip: 312571 bytes, checksum: 1fa2254fa8ecf09b349dca33c7a97323 (MD5) license.txt: 4055 bytes, checksum: 3b546794f918c8a0a7ac693844f093ea (MD5) http://hdl.handle.net/2142/46738 en Copyright 2013 Alina Ene Approximation algorithms Submodular optimization Routing Network design Approximation algorithms for submodular optimization and graph problems text Computer Science 1434 Computer Science 0112 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Computer Science -UIUC 10KS0112PHD