A study on L-extendability of integrally convex functions by linear interpolation

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. In particular, we focus on L-extensibility by linear interpolation and discuss a characterization of integrally convex functions for which such extensions are possible.</p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top