Scaling, proximity, and optimization of integrally convex functions

Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, Fabio Tardella

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


In discrete convex analysis, the scaling and proximity properties for the class of L -convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when n≤ 2 , while a proximity theorem can be established for any n, but only with a superexponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discrete convex function of one variable to the case of integrally convex functions of any fixed number of variables.

Original languageEnglish
Pages (from-to)119-154
Number of pages36
JournalMathematical Programming
Issue number1-2
Publication statusPublished - 2019 May 1

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Scaling, proximity, and optimization of integrally convex functions'. Together they form a unique fingerprint.

Cite this