|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)
Algorithms for M-convex Function Minimization
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
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
we survey the progress on the development of polynomial-time algorithms for
M-convex function minimization.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login