A polynomial oracle-time algorithm for convex integer minimization

Abstract

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex $N$-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex $N$-fold integer minimization problems for which our approach provides polynomial time solution algorithms.

19 pages, 1 figure

References in corpus (2)

• N-Fold Integer Programming
• Test Sets for Integer Programs with Z-Convex Objective

Cited by in corpus (18)

• Nonlinear Integer Programming
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds-Karp to Bland and Beyond
• A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method
• GAMA: A Novel Algorithm for Non-Convex Integer Programs
• Edges vs Circuits: a Hierarchy of Diameters in Polyhedra
• Nash-equilibria and N-fold integer programming
• Quantum Integer Programming (QuIP) 47-779: Lecture Notes
• The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions
• Convex Integer Optimization by Constantly Many Linear Counterparts
• Covering a tree with rooted subtrees
• Multicommodity Flow in Polynomial Time
• Circuit and Graver Walks and Linear and Integer Programming
• The Huge Multiway Table Problem
• Parallel Graver Basis Extraction for Nonlinear Integer Optimization
• A polynomial algorithm for minimizing discrete convic functions in fixed dimension
• N-fold integer programming in cubic time