Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleThe Graver complexity of integer programming.
Author(s) Yael Berstein, Shmuel Onn
TypeArticle in Journal
AbstractIn 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.
KeywordsGraver basis, Gröbner basis, Graver complexity, Markov complexity, contingencytable transportation, polytope
ISSN0218-0006; 0219-3094/e
URL http://link.springer.com/article/10.1007%2Fs00026-009-0029-6
LanguageEnglish
JournalAnn. Comb.
Volume13
Number3
Pages289--296
PublisherSpringer (Birkh\"auser), Basel
Year2009
Edition0
Translation No
Refereed No
Webmaster