CS Colloquium

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). Submodular-function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including Max Cut in digraphs, graphs and hypergraphs, certain constraint satisfaction problems, maximum-entropy sampling, and maximum facility-location problems.

Our main result is that for any k>=2 and any epsilon>0, there is a natural local-search 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/(k-1+epsilon)-approximation, improving a previously known 1/k-approximation. Our analysis can be applied even to general non-monotone submodular maximization subject to k matroid constraints. We show that in this case the approximation guarantee of our algorithm is 1/(k+1+1/(k-1)+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 real-life 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