2026-08-17T15:54:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6836 2024-03-06T10:38:58Z ddc:004 open_access

Scaling and Proximity Properties of Integrally Convex Functions Moriguchi, Satoko Murota, Kazuo Tamura, Akihisa Tardella, Fabio Discrete optimization discrete convexity proximity theorem scaling algorithm In discrete convex analysis, the scaling and proximity properties for the class of L^natural-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 leq 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^natural -convex and integrally convex functions but enjoys the same scaling and proximity properties that hold for L^natural -convex functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Satoko Moriguchi and Kazuo Murota and Akihisa Tamura and Fabio Tardella 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.57 urn:nbn:de:0030-drops-68368 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.57 eng https://creativecommons.org/licenses/by/3.0/legalcode