August 17, 2009
Satoru Iwata
Kyoto University, Japan
Title: Submodular Optimization and Approximation Algorithms
Abstract:
Submodular functions are discrete analogues of convex functions.
Examples include cut capacity functions, matroid rank functions, and entropy functions. Submodular functions can be minimized in polynomial time, which provides a fairly general framework of efficiently solvable combinatorial optimization problems. In contrast, the maximization problems are NP-hard and several approximation algorithms have been developed so far.
In this talk, I will review the above results in submodular optimization and present new approximation algorithms for submodular function minimization under covering constraints. The key technique is the use of discrete convexity of submodular functions in the design of approximation algorithms. This is joint work with Kiyohito Nagano.