Scaling and proximity properties of integrally convex functions

Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, Fabio Tardella

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 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 an exponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discretely convex function in one dimension to the case of integrally convex functions in two dimensions. Furthermore, we identified a new class of discrete convex functions, called directed integrally convex functions, which is strictly between the classes of L-convex and integrally convex functions but enjoys the same scaling and proximity properties that hold for L-convex functions.

Original languageEnglish
Title of host publication27th International Symposium on Algorithms and Computation, ISAAC 2016
EditorsSeok-Hee Hong
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770262
Publication statusPublished - 2016 Dec 1
Event27th International Symposium on Algorithms and Computation, ISAAC 2016 - Sydney, Australia
Duration: 2016 Dec 122016 Dec 14

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other27th International Symposium on Algorithms and Computation, ISAAC 2016


  • Discrete convexity
  • Discrete optimization
  • Proximity theorem
  • Scaling algorithm

ASJC Scopus subject areas

  • Software

Cite this