The Taub Faculty of Computer Science Events and Talks

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 talk, we consider two submodular maximization problems: unconstraint submodular maximization and maximizing a submodular function subject to a down-monotone solvable polytope constraint. Both problems 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. For the first problem we describe a simple linear time combinatorial algorithm achieving the best possible approximation ratio. For the second problem we give a relaxation based algorithm achieving the state of the hard approximation. We also show that the last result induces an optimal algorithm for the Submodular Welfare problem via a simple reduction. Based on joint work with Niv Buchbinder, Joseph (Seffi) Naor and Roy Schwartz.