Ricerc@Sapienza

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.