Akiyoshi Shioura: Minimization of Discrete Convex Functions

The two discrete convexity concepts called M-convexity and L-convexity play primary roles in the theory of discrete convex analysis. In this talk, we consider (unconstrained and constrained) minimization of M-/L-convex functions on the integer lattice points.  We explain various algorithmic approaches for unconstrained minimization of M-/L-convex functions.  We also present some recent results on the approximation algorithms for constrained minimization problems of M-convex functions based on continuous relaxation approach.