Ph.D Thesis | |

Ph.D Student | Feldman Moran |
---|---|

Subject | Maximization Problems with Submodular Objective Functions |

Department | Department of Computer Science |

Supervisor | PROF. Joseph Naor |

Full Thesis text |

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.