文章基本信息

标题：Scaling and Proximity Properties of Integrally Convex Functions
本地全文：下载
作者：Satoko Moriguchi ; Kazuo Murota ; Akihisa Tamura 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：64
页码：57:1-57:13
DOI：10.4230/LIPIcs.ISAAC.2016.57
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Discrete optimization; discrete convexity; proximity theorem; scaling algorithm