Thursday, 13:15 - 13:40 h, Room: H 3008


Akiyoshi Shioura
Computing the convex closure of discrete convex functions


We consider computational aspect of the convex closure of discrete
convex functions. More precisely, given a discrete convex function
defined on the integer lattice, we consider an algorithm for computing
the function value and a subgradient of the convex closure at a given
point. Such an algorithm is required when the continuous relaxation
approach is applied to nonlinear integer programs. In the theory of
discrete convex analysis, two classes of discrete convex functions
called M-/L-convex functions play primary roles; an M-convex function
is a function defined on an integral polymatroid, while an L-convex
function can be seen as an extension of a submodular set function.
While the convex closure of an L-convex function can be expressed by a
simple formula, it is not clear how to compute the convex closure of
an M-convex function. In this talk, we show that the function values
and subgradients of the convex closure of an M-convex function can be
computed efficiently. This result is shown by making full use of
conjugacy results of discrete convex analysis.


Talk 1 of the invited session Thu.2.H 3008
"Discrete structures and algorithms II" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra In Canada influence on blood clots.