Technical Report PHD-2013-08

Title: Maximization Problems with Submodular Objective Functions
Authors: Moran Feldman
Supervisors: Seffi Naor
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2013
To the main CS technical reports page

Computer science department, Technion