[3Xin2] Poster session 1

[3Xin2-35] A study on L-extendability of integrally convex functions by linear interpolation

〇Ken Yokoyama¹, Yuni Iwamasa², Kei Kimura¹, Makoto Yokoo¹ (1.Kyushu University, 2.Kyoto University)

Keywords:Discrete Convex Analysis, Integrally Convex Functions, L-extendability, Half-Integral Relaxation, Simplicial Divisions

Integrally convex functions are a basic class of functions in discrete convex analysis, including M-convex functions and L-convex functions. Recently, the concept of L-extendable functions has been proposed for algorithm development for discrete optimization problems. A function h on an integer lattice is L-extendable if there exists an L-convex function g on a half-integer lattice such that the restriction of g on the integer lattice coincides with that of h. L-extendability is known to be useful in developing approximation algorithms and fast exact algorithms for various discrete optimization problems that are NP-hard. The purpose of this paper is to investigate L-extendability of integrally convex functions. In particular, we focus on L-extensibility by linear interpolation and discuss a characterization of integrally convex functions for which such extensions are possible.