A polynomial oracle-time algorithm for convex integer minimization

DOI10.1007/s10107-009-0276-7zbMath1228.90055arXiv0710.3003OpenAlexW1983610891MaRDI QIDQ623465

Raymond Hemmecke, Robert Weismantel, Shmuel Onn

Publication date: 14 February 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

polynomial time algorithmgreedy augmentation procedure

Mathematics Subject Classification ID

Convex programming (90C25) Integer programming (90C10)

Related Items

The fiber dimension of a graph, Huge Unimodular $n$-Fold Programs, On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond, Solving MIPs via scaling-based augmentation, Minimization of even conic functions on the two-dimensional integral lattice, The quadratic Graver cone, quadratic integer minimization, and extensions, An implementation of steepest-descent augmentation for linear programs, Circuit walks in integral polyhedra, Approximate separable multichoice optimization over monotone systems, A polynomial algorithm for minimizing discrete convic functions in fixed dimension, The power of pyramid decomposition in Normaliz, Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube, \(n\)-fold integer programming in cubic time, \(N\)-fold integer programming and nonlinear multi-transshipment, Unnamed Item, Alternatives for testing total dual integrality, Edges versus circuits: a hierarchy of diameters in polyhedra, Convex integer optimization by constantly many linear counterparts, Constructing Clustering Transformations, Graver basis and proximity techniques for block-structured separable convex integer minimization problems, Cone superadditivity of discrete convex functions, Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes, Robust integer programming, Unnamed Item, A polyhedral model for enumeration and optimization over the set of circuits, Huge multiway table problems, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization, Lower bounds on the graver complexity of \(M\)-fold matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimality criterion for a class of nonlinear integer programs.
• A finiteness theorem for Markov bases of hierarchical models
• \(N\)-fold integer programming
• Decomposition of test sets in stochastic integer programming
• On the positive sums property and the computation of Graver test sets
• Finiteness theorems in stochastic integer programming
• On deviation measures in stochastic integer programming
• A class of games possessing pure-strategy Nash equilibria
• On the foundations of linear and integer linear programming I
• Introduction to Stochastic Programming
• The Complexity of Three-Way Statistical Tables
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs