[2J4-GS-1] Fundamental AI, theory: algorithm

[2J4-GS-1-02] A study on L-extendability of integrally convex functions

〇Ken Yokoyama¹, Kei Kimura¹, Makoto Yokoo¹ (1. Kyushu University)

Keywords:Discrete convex analysis, Integrally convex function, L-extendability, Half-integral relaxation

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. Specifically, we first define a half-integrally convex function on a half-integer lattice that has properties similar to those of an integrally convex function. Then, we investigate the conditions under which an integrally convex function can be relaxed to a half-integrally convex function. Finally, we point out a research direction to investigate the condition under which an integrally convex function is L-extendable.