Ph.D Thesis

Ph.D StudentFeldman Moran
SubjectMaximization Problems with Submodular Objective Functions
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


The study of combinatorial problems with submodular objective functions has attracted much attention recently, and is motivated by the principle of economy of scale, prevalent in real world applications. Moreover, submodular functions are commonly used as utility functions in economics and algorithmic game theory. From a theoretical perspective, submodular functions and submodular optimization play a major role in combinatorics, graph theory and combinatorial optimization.

In this thesis, we consider a few constrained and unconstrained submodular maximization problems. These problems obey the following general structure. Given a submodular function f and (possibly) a set of constraints, find a feasible set S maximizing f(S). The problems we consider in this thesis cannot be solved exactly in polynomial time due to hardness results which are based on information-theoretic arguments. Instead, we describe approximation algorithms for these problems, achieving the best possible approximation ratios for some of the problems.

Our approximation algorithms can be roughly partitioned based on the technique they use. The first approach is combinatorial in nature, and is mostly based on local search techniques and greedy rules. The second approach resembles a common paradigm for designing approximation algorithms, and is composed of two steps. In the first step, a fractional solution is found for a relaxation of the problem. In the second step, the fractional solution is rounded to obtain an integral one while incurring only a small loss in the objective.