Events Calendar

Select a calendar:

Filter October Events by Event Type:

• Conferences, Lectures, & Seminars (6)

Events for October 05, 2010

• Oct

  05

  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). 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