We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The Graver Complexity of Integer Programming.
- Authors
Berstein, Yael; Onn, Shmuel
- 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 K3, m satisfies g( m) = Ω(2 m), with g( m) ≥ 17·2 m−3 –7 for every m > 3.
- Subjects
GROBNER bases; COMMUTATIVE algebra; MARKOV processes; CONTINGENCY tables; INTEGER programming; COMPUTATIONAL complexity
- Publication
Annals of Combinatorics, 2009, Vol 13, Issue 3, p289
- ISSN
0218-0006
- Publication type
Article
- DOI
10.1007/s00026-009-0029-6