[KAIST Discrete Math Seminar] FYI: Colloquium 11/10 Thu 4PM (Satoru Iwata, Submodular Optimization and Approximation Algorithms)

[Sang-il Oum]

***** Colloquium of Dept. of Mathematical Sciences, KAIST *****

DATE: November 10, Thursday

TIME: 4PM-5PM

PLACE: E6-1, ROOM 1501

SPEAKER: Satoru Iwata, RIMS, Kyoto University, Kyoto, Japan

TITLE: Submodular Optimization and Approximation Algorithms

http://mathsci.kaist.ac.kr/~sangil/seminar/entry/20111110/

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.