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.

Scaling, proximity, and optimization of integrally convex functions / Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - STAMPA. - 175:(2019), pp. 119-154. [10.1007/s10107-018-1234-z]

Scaling, proximity, and optimization of integrally convex functions

Tardella, Fabio
Membro del Collaboration Group
2019

Abstract

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.
2019
Discrete Convexity; Integral Convexity; Proximity, Scaling
01 Pubblicazione su rivista::01a Articolo in rivista
Scaling, proximity, and optimization of integrally convex functions / Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - STAMPA. - 175:(2019), pp. 119-154. [10.1007/s10107-018-1234-z]
File allegati a questo prodotto
File Dimensione Formato  
Tardella_ Scaling-proximity-optimization_2019.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 672.95 kB
Formato Adobe PDF
672.95 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1077222
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 10
social impact