(Colloquium) Satoru Iwata, Submodular Optimization and Approximation Algorithms

Submodular Optimization and Approximation Algorithms
Satoru Iwata
RIMS, Kyoto University, Kyoto, Japan
2011/11/10 Thu 4PM-5PM
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 recent approximation algorithms for combinatorial optimization problems described in terms of submodular functions.

Tags: ,

Comments are closed.