A study on L-extendability of integrally convex functions

DOI

Bibliographic Information

Other Title
  • 整凸関数におけるL拡張可能性に関する一考察

Description

<p>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.</p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top