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

**Akiyoshi Shioura**

Computing the convex closure of discrete convex functions

**Abstract:**

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"** [...]