Speaker: Alina Ena
University of Illinois
Title: Submodular cost allocation: applications, algorithms and hardness results
Discrete optimization problems follow a common template: given a set function f on a ground set V, find the subset S of V that maximizes or minimizes f(S) subject to certain constraints on S. If f is a linear function, this framework captures fundamental combinatorial optimization problems. In this talk, we consider optimization problems in which the function f belongs to the more general class of submodular functions. Submodular optimization problems are motivated by several applications and they are of mathematical interest.
In this talk, we identify a class of submodular minimization problems that are tractable. We introduce a model that captures allocation problems with submodular costs and we give a generic approach for designing approximation algorithms for problems in this model. Our model captures several problems of interest, such as non-metric facility location, multiway cut problems in graphs and hypergraphs, uniform metric labeling and its generalization to hub location. We describe a convex-programming relaxation obtained via the Lovasz extension of a submodular function. This allows us to understand several previous relaxations and rounding procedures in a uniﬁed fashion and also develop new formulations and approximation algorithms for several problems. We complement our algorithmic results with hardness of approximation results for some of the problems in this model.
This talk is based on joint work with Chandra Chekuri, Jan Vondrak, and Yi Wu.