Approximation algorithms for submodular optimization and graph problems

Approximation algorithms;Submodular optimization;Routing;Network design

Ene, Alina

关键词: Approximation algorithms;    Submodular optimization;    Routing;    Network design;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/46738/Alina_Ene.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

In this thesis, we consider combinatorial optimization problemsinvolving submodular functions and graphs. The problems we study areNP-hard and therefore, assuming that P =/= NP, there donot exist polynomial-time algorithms that always output an optimalsolution. 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, forany instance of the problem, it outputs a solution whose value iswithin a multiplicative factor p of the value of the optimalsolution for the instance. The quantity p is the approximationratio of the algorithm and we aim to achieve the smallest ratiopossible.Our focus in this thesis is on designing approximation algorithms forseveral combinatorial optimization problems. In the first part ofthis thesis, we study a class of constrained submodular minimizationproblems.We introduce a model that captures allocationproblems with submodular costs and we give a generic approach fordesigning approximation algorithms for problems in this model. Ourmodel captures several problems of interest, such as non-metricfacility location, multiway cut problems in graphs and hypergraphs,uniform metric labeling and its generalization to hub location. Usinga convex relaxation and rounding strategy, we achieve goodapproximation guarantees for several problems in this model. Inparticular, we match or improve the known approximation ratios forseveral problems in a unified fashion.In the second part of this thesis, we study muticommodity flowproblems in both undirected and directed graphs and we make severalcontributions towards understanding the gap between fractional andintegral multicommodity flows. We give a poly-logarithmicapproximation with constant congestion for the node-disjoint pathsproblem and we show a poly-logarithmic upper bound on the gap betweenthe maximum fractional and integral throughput flows innode-capacitated undirected graphs.Prior to our work, the bestguarantees were only polynomial. In the process, we prove aconjecture of Chekuri, Khanna, and Shepherd on the connection betweenthe treewidth of the graph and the existence of a good routingstructure. Additionally, we initiate the study of integral throughputflow problems in directed graphs with symmetric demand pairs. Weobtain a poly-logarithmic approximation with constant congestion forthe all-or-nothing flow problem.In the third part of this thesis, we study several network designproblems. The input to these problems is a graph with costs on theedges or the nodes and the output is a minimum cost subgraphthat meets certain connectivity requirements.We study several network design problems in planar graphs,including the prize-collecting Steiner tree and forest and thesurvivable network design problem with node costs. We show that thespecial structure of planar graphs --- and more generally, boundedgenus and minor-free graphs --- leads to algorithms whoseapproximation guarantees are a significant improvement over what canbe achieved for general graphs.