Eastern Great Lakes Theory Workshop Talk

Algorithms for Max-min Optimization

Anupam Gupta, Carnegie Mellon University

Sunday, October 10, 9:00-10:00am

ABSTRACT

There has been much recent work on maximizing submodular functions subject to side-constraints: e.g., maximize f(S) subject to the size of S being at most k. However, much less is known when f is not a submodular function, or is not even close to submodularity. In this talk, we will present some recent results where f(S) is defined by a covering (minimization) problem, but is far from submodular.

As a concrete example, consider the following set-cover-like question: you are given a set system (U,F), and want to find S, a subset of the universe U, of size at most k, such that the minimum cost to cover S using the sets from the family F is maximized. Our techniques give an O(log m + log n)-approximation for this problem, which is near-optimal.

Slides

Speaker Bio

Anupam Gupta is an Associate Professor at the Computer Science Department at Carnegie Mellon University, Pittsburgh PA. He received his B.Tech degree in Computer Science from Indian Institute of Technology, Kanpur in 1996, and his doctorate in Computer Science from the University of California, Berkeley, in 2000. After two years in the Mathematical Sciences Department at Lucent Bell Labs in Murray Hill, New Jersey, he joined Carnegie Mellon University in January 2003, where he has been since. His research interests are in theoretical Computer Science, primarily in developing approximation algorithms for NP-hard optimization problems, and understanding the algorithmic properties of metric spaces. He is the recipient of an Alfred P. Sloan Research Fellowship, and the NSF Career award.

< Schedule < EaGL-III homepage