<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
The Graver Complexity of Integer Programming
Yael Berstein and Shmuel Onn
Faculty of Industrial Engineering and Management, Technion-Israel Institute of Technology, Technion, Haifa 32000, Israel
yaelber@tx.technion.ac.il, onn@ie.technion.ac.il
Annals of Combinatorics 13 (3) pp.289-296 September, 2009
AMS Subject Classification: 05A, 15A, 51M, 52A
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(2m), with g(m)> 17• 2{m-3}-7 for every m>3.
Keywords: Graver basis, Grobner basis, Graver complexity, Markov complexity, contingency table, transportation polytope, transportation problem, integer programming, computational complexity


1. Aoki, S., Takemura, A.: Minimal basis for connected Markov chain over 3*3*k contingency tables with fixed two-dimensional marginals. Aust. N. Z. J. Stat. 45, 229-249 (2003)

2. De Loera, J., Hemmecke, R., Onn, S., Weismantel, R.: N-fold integer programming. Discrete Optim. 5, 231-–241 (2008)

3. De Loera, J., Onn, S.: All linear and integer programs are slim 3-way transportation programs. SIAM J. Optim. 17, 806-821 (2006)

4. De Loera, J., Onn, S.: Markov bases of three-way tables are arbitrarily complicated. J. Symbolic Comput. 41, 173-181 (2006)

5. Gordan, P.: U¨ ber die Auo¨sung linearer Gleichungen mit reellen Coeficienten. Math. Ann. 6, 23-28 (1873)

6. Graver, J.E.: On the foundations of linear and integer programming. Math. Program. 9, 207-–226 (1975)

7. Hemmecke, R., Nairn, K.A.: On the Gr¨obner complexity of matrices. J. Pure Appl. Algebra 213, 1558-–1563 (2009)

8. Santos, F., Sturmfels, B.: Higher Lawrence configurations. J. Combin. Therory Ser. A 103, 151-–164 (2003)

9. Sturmfels, B.: Gr¨obner Bases and Convex Polytopes. American Mathematical Society, Providence (1996)