{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:41:35Z","timestamp":1725892895113},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540660194"},{"type":"electronic","value":"9783540487777"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48777-8_11","type":"book-chapter","created":{"date-parts":[[2007,3,2]],"date-time":"2007-03-02T08:43:11Z","timestamp":1172824991000},"page":"137-150","source":"Crossref","is-referenced-by-count":16,"title":["Bounds on the Chv\u00e1tal Rank of Polytopes in the 0\/1-Cube"],"prefix":"10.1007","author":[{"given":"Friedrich","family":"Eisenbrand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,4,30]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1006\/jcta.1997.2780","volume":"79A","author":"N. Alon","year":"1997","unstructured":"N. Alon and V. H. Vu. Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs. Journal of Combinatorial Theory, 79A:133\u2013160, 1997.","journal-title":"Journal of Combinatorial Theory"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6377(96)00007-7","volume":"19","author":"E. Balas","year":"1996","unstructured":"E. Balas, S. Ceria, G. Cornu\u00e9jols, and N. R. Natraj. Gomory cuts revisited. Operations Research Letters, 19:1\u20139, 1996.","journal-title":"Operations Research Letters"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0166-218X(89)90014-0","volume":"23","author":"E. Balas","year":"1989","unstructured":"E. Balas and M. J. Saltzman. Facets of the three-index assignment polytope. Discrete Applied Mathematics, 23:201\u2013229, 1989.","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1287\/moor.10.2.340","volume":"10","author":"F. Barahona","year":"1985","unstructured":"F. Barahona, M. Gr\u00f6tschel, and A. R. Mahjoub. Facets of the bipartite subgraph polytope. Mathematics of Operations Research, 10:340\u2013358, 1985.","journal-title":"Mathematics of Operations Research"},{"key":"11_CR5","unstructured":"A. Bockmayr and F. Eisenbrand. On the Chv\u00e1tal rank of polytopes in the 0\/1 cube. Research Report MPI-I-97-2-009, Max-Planck-Institut f\u00fcr Informatik, September 1997."},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"A. Bockmayr, F. Eisenbrand, M. E. Hartmann, and A. S. Schulz. On the Chv\u00e1tal rank of polytopes in the 0\/1 cube. Technical Report 616, Technical University of Berlin, Department of Mathematics, December 1998.","DOI":"10.1016\/S0166-218X(99)00156-0"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"708","DOI":"10.2307\/2275569","volume":"62","author":"M. Bonet","year":"1997","unstructured":"M. Bonet, T. Pitassi, and R. Raz. Lower bounds for cutting planes proofs with small coefficients. Journal of Symbolic Logic, 62:708\u2013728, 1997.","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR8","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/moor.16.2.259","volume":"16","author":"S. C. Boyd","year":"1991","unstructured":"S. C. Boyd and W. H. Cunningham. Small travelling salesman polytopes. Mathematics of Operations Research, 16:259\u2013271, 1991.","journal-title":"Mathematics of Operations Research"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1137\/0805020","volume":"5","author":"S. C. Boyd","year":"1995","unstructured":"S. C. Boyd, W. H. Cunningham, M. Queyranne, and Y. Wang. Ladders for travelling salesmen. SIAM Journal on Optimization, 5:408\u2013420, 1995.","journal-title":"SIAM Journal on Optimization"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01588786","volume":"49","author":"S. C. Boyd","year":"1991","unstructured":"S. C. Boyd and W. R. Pulleyblank. Optimizing over the subtour polytope of the travelling salesman problem. Mathematical Programming, 49:163\u2013187, 1991.","journal-title":"Mathematical Programming"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V. Chv\u00e1tal","year":"1973","unstructured":"V. Chv\u00e1tal. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics, 4:305\u2013337, 1973.","journal-title":"Discrete Mathematics"},{"key":"11_CR12","doi-asserted-by":"crossref","first-page":"33","DOI":"10.4153\/CMB-1973-008-9","volume":"16","author":"V. Chv\u00e1tal","year":"1973","unstructured":"V. Chv\u00e1tal. Flip-flops in hypohamiltonian graphs. Canadian Mathematical Bulletin, 16:33\u201341, 1973.","journal-title":"Canadian Mathematical Bulletin"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114\/115","author":"V. Chv\u00e1tal","year":"1989","unstructured":"V. Chv\u00e1tal, W. Cook, and M. E. Hartmann. On cutting-plane proofs in combinatorial optimization. Linear Algebra and its Applications, 114\/115:455\u2013499, 1989.","journal-title":"Linear Algebra and its Applications"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"W. Cook, C. R. Coullard, and Gy. Tur\u00e1n. On the complexity of cutting plane proofs. Discrete Applied Mathematics, 18:25\u201338, 1987.","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"W. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver. Combinatorial Optimization. John Wiley, 1998.","DOI":"10.1002\/9781118033142"},{"key":"11_CR16","unstructured":"F. Eisenbrand. A note on the membership problem for the first elementary closure of a polyhedron. Technical Report 605, Technical University of Berlin, Department of Mathematics, November 1998. To appear in Combinatorica."},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1112\/S0025579300003260","volume":"9","author":"P. Erd\u00f6s","year":"1962","unstructured":"P. Erd\u00f6s. On circuits and subgraphs of chromatic graphs. Mathematika, 9:170\u2013175, 1962.","journal-title":"Mathematika"},{"key":"11_CR18","unstructured":"M. Fischetti. Three facet lifting theorems for the asymmetric traveling salesman polytope. In E. Balas, G. Cournu\u00e9jols, and R. Kannan, editors, Integer Programming and Combinatorial Optimization, pages 260\u2013273. Proceedings of the 2nd IPCO Conference, 1992."},{"key":"11_CR19","unstructured":"T. Fleiner, V. Kaibel, and G. Rote. Upper bounds on the maximal number of facets of 0\/1-polytopes. Technical Report 98-327, University of Cologne, Department of Computer Science, 1998. To appear in European Journal of Combinatorics."},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0095-8956(81)90033-2","volume":"31","author":"R. Giles","year":"1981","unstructured":"R. Giles and L. E. Trotter. On stable set polyhedra for K 1,3-free graphs. Journal of Combinatorial Theory, 31:313\u2013326, 1981.","journal-title":"Journal of Combinatorial Theory"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"R. E. Gomory","year":"1958","unstructured":"R. E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64:275\u2013278, 1958.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"11_CR22","unstructured":"R. E. Gomory. An algorithm for integer solutions to linear programs. In R. L. Graves and P. Wolfe, editors, Recent Advances in Mathematical Programming, pages 269\u2013302. McGraw-Hill, 1963."},{"key":"11_CR23","unstructured":"M. Gr\u00f6tschel and M. W. Padberg. Polyhedral theory. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnoy Kan, and D. B. Shmoys, editors, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pages 251\u2013305. John Wiley, 1985."},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1287\/moor.11.4.537","volume":"11","author":"M. Gr\u00f6tschel","year":"1986","unstructured":"M. Gr\u00f6tschel and W. R. Pulleyblank. Clique tree inequalities and the symmetric travelling salesman problem. Mathematics of Operations Research, 11:537\u2013569, 1986.","journal-title":"Mathematics of Operations Research"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"A. Haken. The intractability of resolution. Theoretical Computer Science, 39:297\u2013308, 1985.","journal-title":"Theoretical Computer Science"},{"key":"11_CR26","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF01580442","volume":"8","author":"P. L. Hammer","year":"1975","unstructured":"P. L. Hammer, E. Johnson, and U. N. Peled. Facets of regular 0\u20131 polytopes. Mathematical Programming, 8:179\u2013206, 1975.","journal-title":"Mathematical Programming"},{"key":"11_CR27","unstructured":"M. E. Hartmann. Cutting planes and the complexity of the integer hull. Technical Report 819, School of Operations Research and Industrial Engineering, Cornell University, September 1988."},{"key":"11_CR28","unstructured":"M. E. Hartmann. Personal communication, March 1998."},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"M. E. Hartmann, M. Queyranne, and Y. Wang. On the Chv\u00e1tal rank of certain inequalities. This volume, 1999.","DOI":"10.1007\/3-540-48777-8_17"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, T. Pitassi, and A. Urquhart. Upper and lower bound for tree-like cutting plane proofs. In Proc. Logic in Computer Science, LICS\u201994, Paris, 1994.","DOI":"10.1109\/LICS.1994.316069"},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/PL00009303","volume":"17","author":"U. H. Kortenkamp","year":"1997","unstructured":"U. H. Kortenkamp, J. Richter-Gebert, A. Sarangarajan, and G. M. Ziegler. Extremal properties of 0\/1-polytopes. Discrete and Computational Geometry, 17:439\u2013448, 1997.","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR32","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01589099","volume":"45","author":"D. Naddef","year":"1989","unstructured":"D. Naddef. The Hirsch conjecture is true for (0,1)-polytopes. Mathematical Programming, 45:109\u2013110, 1989.","journal-title":"Mathematical Programming"},{"key":"11_CR33","unstructured":"M. W. Padberg and M. Gr\u00f6tschel. Polyhedral computations. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnoy Kan, and D. B. Shmoys, editors, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pages 307\u2013360. John Wiley, 1985."},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P. Pudl\u00e1k","year":"1997","unstructured":"P. Pudl\u00e1k. Lower bounds for resolution and cutting plane proofs and monotone computations. Journal of Symbolic Logic, 62:981\u2013988, 1997.","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR35","doi-asserted-by":"crossref","unstructured":"W. R. Pulleyblank. Polyhedral combinatorics. In G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd, editors, Optimization, Volume 1 of Handbooks in Operations Research and Management Science, Chapter V, pages 371\u2013446. Elsevier, 1989.","DOI":"10.1016\/S0927-0507(89)01006-6"},{"key":"11_CR36","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0167-5060(08)70085-2","volume":"9","author":"A. Schrijver","year":"1980","unstructured":"A. Schrijver. On cutting planes. Annals of Discrete Mathematics, 9:291\u2013296, 1980.","journal-title":"Annals of Discrete Mathematics"},{"key":"11_CR37","unstructured":"A. Schrijver. Theory of Linear and Integer Programming. John Wiley, 1986."},{"key":"11_CR38","volume-title":"Polytopes and Scheduling","author":"A. S. Schulz","year":"1996","unstructured":"A. S. Schulz. Polytopes and Scheduling. PhD thesis, Technical University of Berlin, Berlin, Germany, 1996."},{"key":"11_CR39","unstructured":"A. S. Schulz. A simple proof that the Chv\u00e1tal rank of polytopes in the 0\/1-cube is small. Unpublished manuscript, September 1997."},{"key":"11_CR40","unstructured":"A. S. Schulz, R. Weismantel, and G. M. Ziegler. An optimization problem is ten problems. In preparation."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48777-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T22:19:09Z","timestamp":1556144349000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48777-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540660194","9783540487777"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-48777-8_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}