The Graver Complexity of Integer Programming |
| |
Authors: | Yael Berstein Shmuel Onn |
| |
Institution: | (3) Technion – Israel Institute of Technology, Haifa, Israel; |
| |
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) = Ω(2
m
), with g(m) ≥ 17·2
m−3 –7 for every m > 3. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|