The Graver complexity of integer programming

DOI10.1007/s00026-009-0029-6zbMath1231.90295arXiv0709.1500OpenAlexW2078515884MaRDI QIDQ659795

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 complexityinteger programmingGröbner basistransportation problemGraver basisGraver complexitytransportation polytopecontingencytableMarkov complexity

Mathematics Subject Classification ID

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

Related Items (10)

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 ⋮ The quadratic Graver cone, quadratic integer minimization, and extensions ⋮ The Markov complexity of book graphs ⋮ \(n\)-fold integer programming in cubic time ⋮ \(N\)-fold integer programming and nonlinear multi-transshipment ⋮ Asymptotic behavior of Markov complexity ⋮ Unboundedness of Markov complexity of monomial curves in \(\mathbb{A}^n\) for \(n \geq 4\) ⋮ Convex integer maximization via Graver bases ⋮ Lower bounds on the graver complexity of \(M\)-fold matrices

Cites Work

• \(N\)-fold integer programming
• On the Gröbner complexity of matrices
• Higher Lawrence configurations.
• Markov bases of three-way tables are arbitrarily complicated
• On the foundations of linear and integer linear programming I
• Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Unnamed Item

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