Optimizing Submodular Functions (Masters project):

Given a ground set S, a set function f is a function assigning a real number for each subsets of S. Submodular functions form a natural class of sets functions appearing in many fields such as graph theory, economics and game theory. Optimization of submodular function under various constraints has received a lot of interest in recent years. This project involves looking for two kinds of “bad” instances of submodular optimization problems:

1. The state of the art algorithm for maximizing a non-negative submodular function subject to a polytope constraint is known to have an approximation ratio of at least 1/e (0.367). We are looking for a tight example showing that this is the best approximation ratio that can be proved for this specific algorithm.


2. Many basic submodular optimization problems still have a significant gap between the state of the art algorithms and hardness results. One technique for proving hardness results for these problems works as following: if one can give an instance where there is a significant gap between the best solution and the best symmetric solution (i.e., solution that is unchanged by permutations of the ground set that map the instance into itself up to renaming of ground set elements), then this gap can be translated into a hardness using known mathematical machinery. Thus, we are looking for instances demonstrating gaps of the above kind which is larger than the state of the hard hardness of the corresponding problems.

Further questions about the project: moran.feldman "at" epfl.ch

Responsible professor: Ola Svensson

Back to Theory@EPFL.