The Graver complexity of integer programming

DOI10.1007/S00026-009-0029-6MaRDI QIDQ659795zbMATH OpenOpenAlexFDO

Authors Yael Berstein, Shmuel Onn

Publication date 24 January 2012

Published in Annals of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycontingencytableGraver basisGraver complexityGröbner basisinteger programmingMarkov complexitytransportation polytopetransportation problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Integer programming (90C10)

Abstract: In this article we establish an exponential lower bound on the Graver complexity of integer programs. This provides new type of evidence supporting the presumable intractability of integer programming. Specifically, we show that the Graver complexity of the incidence matrix of the complete bipartite graph $K_{3,m}$ satisfies $g(m)=Omega(2^m)$, with $g(m)geq17cdot{2}^{m-3}-7$ for every $m>3$ .

Recommendations

• A lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph
• Lower bounds on the graver complexity of M-fold matrices
• Integer programming and incidence treedepth
• On the Graver complexity of codimension \(2\) matrices
• The computational complexity of integer programming with alternations

Cites work

• \(N\)-fold integer programming
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Higher Lawrence configurations.
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• Markov bases of three-way tables are arbitrarily complicated
• Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
• On the foundations of linear and integer linear programming I
• On the Gröbner complexity of matrices

Cited in

(15)

• Convex integer maximization via Graver bases
• Robust integer programming
• The quadratic Graver cone, quadratic integer minimization, and extensions
• \(n\)-fold integer programming in cubic time
• Unboundedness of Markov complexity of monomial curves in \(\mathbb{A}^n\) for \(n \geq 4\)
• Lower bounds on the graver complexity of M-fold matrices
• The Markov complexity of book graphs
• Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• Asymptotic behavior of Markov complexity
• \(N\)-fold integer programming and nonlinear multi-transshipment
• Markov Bases: A 25 Year Update
• Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
• Does subset sum admit short proofs?
• On the Graver complexity of codimension \(2\) matrices

This page was built for publication: The Graver complexity of integer programming

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