A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation

2011/09/19 by Amitabh Basu, Basu, Amitabh, Robert Hildebrand +5
Mathematics · #90C10 #90C11 #Advanced Combinatorial Mathematics #Advanced Operator Algebra Research #Algebraic structures and combinatorial models #FOS: Mathematics #Optimization and Control (math.OC) #math.OC #msc:90C10 #msc:90C11

paper · pdf · doi:10.48550/arxiv.1109.4184

25 pages, 2 figures

arxiv created 2011/09/19 · openalex publication_date 2011/09/19 · arxiv updated 2011/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.

Related

• Extreme functions with an arbitrary number of slopes
• All Cyclic Group Facets Inject
• Approximation of Minimal Functions by Extreme Functions
• An extreme function which is nonnegative and discontinuous everywhere
• An Electronic Compendium of Extreme Functions for the Gomory--Johnson Infinite Group Problem