A polynomial oracle-time algorithm for convex integer minimization
From MaRDI portal
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 -fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex -fold integer minimization problems for which our approach provides polynomial time solution algorithms.
Recommendations
- scientific article; zbMATH DE number 953034
- A fully polynomial time approximation algorithm for convex multiplicative problems
- An algorithm for concave integer minimization over a polyhedron
- scientific article; zbMATH DE number 5925034
- A polynomial algorithm for minimizing discrete convic functions in fixed dimension
- Complexity of integer quasiconvex polynomial optimization
- Integer conic function minimization based on the comparison oracle
- On the complexity of quasiconvex integer minimization problem
- An algorithm and new penalties for concave integer minimization over a polyhedron
- On the optimality of pseudo-polynomial algorithms for integer programming
Cites work
- scientific article; zbMATH DE number 1688599 (Why is no real title available?)
- scientific article; zbMATH DE number 1305542 (Why is no real title available?)
- A class of games possessing pure-strategy Nash equilibria
- A finiteness theorem for Markov bases of hierarchical models
- All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
- Decomposition of test sets in stochastic integer programming
- Finiteness theorems in stochastic integer programming
- Introduction to Stochastic Programming
- Network flows. Theory, algorithms, and applications.
- On deviation measures in stochastic integer programming
- On the foundations of linear and integer linear programming I
- On the positive sums property and the computation of Graver test sets
- Optimality criterion for a class of nonlinear integer programs.
- The Complexity of Three-Way Statistical Tables
- \(N\)-fold integer programming
Cited in
(33)- Combinatorial \(n\)-fold integer programming and applications
- Huge multiway table problems
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- Lower bounds on the graver complexity of M-fold matrices
- Minimization of even conic functions on the two-dimensional integral lattice
- Constructing Clustering Transformations
- The fiber dimension of a graph
- scientific article; zbMATH DE number 1445399 (Why is no real title available?)
- Cone superadditivity of discrete convex functions
- Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes
- Robust integer programming
- Solving MIPs via scaling-based augmentation
- Pivot rules for circuit-augmentation algorithms in linear optimization
- \(N\)-fold integer programming and nonlinear multi-transshipment
- Integer convex minimization by mixed integer linear optimization
- Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube
- Approximate separable multichoice optimization over monotone systems
- The quadratic Graver cone, quadratic integer minimization, and extensions
- The power of pyramid decomposition in Normaliz
- An implementation of steepest-descent augmentation for linear programs
- Convex integer optimization by constantly many linear counterparts
- A polyhedral model for enumeration and optimization over the set of circuits
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- scientific article; zbMATH DE number 7651172 (Why is no real title available?)
- Huge unimodular \(n\)-fold programs
- \(n\)-fold integer programming in cubic time
- Edges versus circuits: a hierarchy of diameters in polyhedra
- Circuit and Graver walks and linear and integer programming
- Circuit walks in integral polyhedra
- A polynomial algorithm for minimizing discrete convic functions in fixed dimension
- Alternatives for testing total dual integrality
- Convex discrete optimization
- Oracle-polynomial-time approximation of largest simplices in convex bodies
This page was built for publication: A polynomial oracle-time algorithm for convex integer minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q623465)
