Approximation of minimal functions by extreme functions

DOI10.1137/17M1143605MaRDI QIDQ5376455zbMATH OpenOpenAlexWikidataFDO

Authors Teresa M. Lebair, Amitabh Basu

Publication date 18 September 2018

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.04344

zbMATH Keywords

cut-generating functionsextreme functionsinfinite group relaxationinteger programming

Mathematics Subject Classification ID

Approximation with constraints (41A29) Multidimensional problems (41A63) Integer programming (90C10)

Abstract: In a recent paper, Basu, Hildebrand, and Molinaro established that the set of continuous minimal functions for the 1-dimensional Gomory-Johnson infinite group relaxation possesses a dense subset of extreme functions. The $n$-dimensional version of this result was left as an open question. In the present paper, we settle this query in the affirmative: for any integer $ngeq1$, every continuous minimal function can be arbitrarily well approximated by an extreme function in the $n$-dimensional Gomory-Johnson model.

Recommendations

• Equivariant perturbation in Gomory and Johnson's infinite group problem. I: The one-dimensional case

Cites work

• A (k+1)-slope theorem for the k-dimensional infinite group relaxation
• A geometric approach to cut-generating functions
• A geometric perspective on lifting
• Convex Analysis
• scientific article; zbMATH DE number 3555734 (Why is no real title available?)
• scientific article; zbMATH DE number 3303053 (Why is no real title available?)
• Introduction to Piecewise Differentiable Equations
• Lectures on Polytopes
• Some continuous functions related to corner polyhedra
• Some continuous functions related to corner polyhedra, II

Cited in

(4)

• On the minimization of possibly discontinuous functions by means of pointwise approximations
• Minimal approximations and Norton's dome
• scientific article; zbMATH DE number 6533282 (Why is no real title available?)
• scientific article; zbMATH DE number 18487 (Why is no real title available?)

Describes a project that uses

Uses Software

• infinite group relaxation

This page was built for publication: Approximation of minimal functions by extreme functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5376455)