
CS Colloquium
Tue, Oct 05, 2010 @ 03:30 PM  05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Maxim Sviridenko , IBM Watson
Talk Title: Local Search Algorithms for Submodular Maximization
Abstract: We study the problem of maximizing a submodular function over the intersection of k matroids (for a constant k>=2). Submodularfunction maximization is a central problem in combinatorial optimization, generalizing many important NPhard problems including Max Cut in digraphs, graphs and hypergraphs, certain constraint satisfaction problems, maximumentropy sampling, and maximum facilitylocation problems.
Our main result is that for any k>=2 and any epsilon>0, there is a natural localsearch algorithm which has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves a 1/(k+1)approximation of Nemhauser, Wolsey and Fisher from 1978. For maximizing a linear function over k matroids, we obtain a 1/(k1+epsilon)approximation, improving a previously known 1/kapproximation. Our analysis can be applied even to general nonmonotone submodular maximization subject to k matroid constraints. We show that in this case the approximation guarantee of our algorithm is 1/(k+1+1/(k1)+epsilon), improving the previously known factor of 1/(k+2+1/k+epsilon).
Biography: Maxim Sviridenko is a research stuff member in the Algorithms group of the Optimization Center in the Department of Business Analytics and Mathematical Sciences of the IBM T.J. Watson Research Center. He received his Ph.D. in Applied Mathematics and Computer Science from the Sobolev Institute of Mathematics (Russia) in 1999. After that he held two postdoc positions: in the Department of Commerce and Business Administration (UBC, Canada) and Computer Science Department at the University of Aarhus Denmark) before joining IBM Research in 2000. His research interests include design and analysis of algorithms for discrete optimization problems, computational complexity, integer and linear programming, modelling reallife optimization problems arising in various industrial applications and developing algorithms to solve such problems. Recently, he has been working on analyzing the local search algorithms that is one of the most popular approaches to solve optimization problems in practice.
Host: Dr. David Kempe
Location: Seaver Science Library (SSL)  150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal