APPROXIMATION ALGORITHMS FOR SUBMODULAR OPTIMIZATION AND GRAPH PROBLEMS

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 6 = 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 ρ of the value of the optimal solution for the instance. The quantity ρ 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 generalizatio