Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Friday, April 21, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Akiyoshi Shioura (Tohoku Univ., Japan and Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
In the area of discrete optimization, one of the important topics is to
identify the discrete structure that guarantees the success of greedy
As an attempt to do this, various researchers have proposed discrete analogues of convex functions, or "discrete convex" functions. Among them, the concept of M-convex functions, introduced by Murota (1996) affords a nice framework for well-solved discrete optimization problems with nonlinear objective functions such as the nonlinear resource allocation problem and the convex cost flow problem. M-convex function is a generalization of separable convex function over a polymatroid as well as valuated matroid by Dress-Wenzel (1990). Also, M-convex functions enjoy various desirable properties as "discrete convexity" such as extendibility to ordinary convex functions, conjugacy, duality, etc.
In this talk, we consider the minimization of an M-convex function. It is a fundamental problem concerning M-convex functions, and several algorithms have been proposed so far. After a brief summary of background and fundamental results of M-convex function, we survey the progress on the development of polynomial-time algorithms for M-convex function minimization.
Automatic MiSe System Software Version 1.4803M | admin login