Submodular Optimization and Approximation Algorithms

Satoru Iwata

RIMS, Kyoto University, Kyoto, Japan

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.

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: colloquium, SatoruIwata