{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:33:05Z","timestamp":1725485585427},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_8","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T02:58:05Z","timestamp":1181185085000},"page":"82-96","source":"Crossref","is-referenced-by-count":6,"title":["Combinatorial Linear Programming: Geometry Can Help"],"prefix":"10.1007","author":[{"given":"Bernd","family":"G\u00e4rtner","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1287\/moor.1.1.89","volume":"1","author":"I. Adler","year":"1976","unstructured":"I. Adler and R. Saigal. Long monotone paths in abstract polytopes. Math. Operations Research, 1(1):89\u201395, 1976.","journal-title":"Math. Operations Research"},{"doi-asserted-by":"crossref","unstructured":"N. Amenta and G. M. Ziegler. Deformed products and maximal shadows. In J. Chazelle, J.B. Goodman, and R. Pollack, editors, Advances in Discrete and Computational geometry, Contemporary Mathematics. Amer. Math. Soc, 1998.","key":"8_CR2","DOI":"10.1090\/conm\/223\/03132"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0012-365X(93)E0134-P","volume":"137","author":"D. Barnette","year":"1995","unstructured":"D. Barnette. A short proof of the d-connectedness of d-polytopes. Discrete Math., 137:351\u2013352, 1995.","journal-title":"Discrete Math."},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1287\/moor.2.2.103","volume":"2","author":"R. G. Bland","year":"1977","unstructured":"R. G. Bland. New finite pivoting rules for the simplex method. Math. Operations Research, 2:103\u2013107, 1977.","journal-title":"Math. Operations Research"},{"key":"8_CR5","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"V. Chv\u00e1tal. Linear Programming. W. H. Freeman, New York, NY, 1983."},{"key":"8_CR6","volume-title":"Linear Programming and Extensions","author":"G. B. Dantzig","year":"1963","unstructured":"G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, 1963."},{"unstructured":"B. G\u00e4rtner. Randomized Optimization by Simplex-Type Methods. PhD thesis, Freie Universit\u00e4t Berlin, 1995.","key":"8_CR7"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1137\/S0097539793250287","volume":"24","author":"B. G\u00e4rtner","year":"1995","unstructured":"B. G\u00e4rtner. A subexponential algorithm for abstract optimization problems. SIAM J. Comput., 24:1018\u20131035, 1995.","journal-title":"SIAM J. Comput."},{"unstructured":"B. G\u00e4rtner, M. Henk, and G. M. Ziegler. Randomized simplex algorithms on Klee-Minty cubes. Combinatorica (to appear).","key":"8_CR9"},{"key":"8_CR10","volume-title":"Technical Report TR 296","author":"B. G\u00e4rtner","year":"1998","unstructured":"B. G\u00e4rtner and V. Kaibel. Abstract objective function graphs on the 3-cube-a characterization by realizability. Technical Report TR 296, Dept. of Computer Science, ETH Z\u00fcrich, 1998."},{"key":"8_CR11","series-title":"Lect Notes Comput Sci","first-page":"669","volume-title":"Proc. 13th annu. Symp. on Theoretical Aspects of Computer Science (STAGS)","author":"B. G\u00e4rtner","year":"1996","unstructured":"B. G\u00e4rtner and E. Welzl. Linear programming-randomization and abstract frameworks. In Proc. 13th annu. Symp. on Theoretical Aspects of Computer Science (STAGS), volume 1046 of Lecture Notes in Computer Science, pages 669\u2013687. Springer-Verlag, 1996."},{"doi-asserted-by":"crossref","unstructured":"D. Goldfarb. On the complexity of the simplex algorithm. In S. Gomez, editor, IV. Workshop on Numerical Analysis and Optimization, Oaxaca, Mexico, 1993.","key":"8_CR12","DOI":"10.1007\/978-94-015-8330-5_2"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0166-218X(88)90042-X","volume":"20","author":"K. Williamson Hoke","year":"1988","unstructured":"K. Williamson Hoke. Completely unimodal numberings of a simple polytope. Discr. Applied Math., 20:69\u201381, 1988.","journal-title":"Discr. Applied Math."},{"doi-asserted-by":"crossref","unstructured":"F. Holt and V. Klee. A proof of the strict monotone 4-step conjecture. In J. Chazelle, J.B. Goodman, and R. Pollack, editors, Advances in Discrete and Computational geometry, Contemporary Mathematics. Amer. Math. Soc, 1998.","key":"8_CR14","DOI":"10.1090\/conm\/223\/03138"},{"doi-asserted-by":"crossref","unstructured":"G. Kalai. A subexponential randomized simplex algorithm. In Proc. 24th annu. ACM Symp. on Theory of Computing., pages 475\u2013482, 1992.","key":"8_CR15","DOI":"10.1145\/129712.129759"},{"key":"8_CR16","first-page":"217","volume":"79","author":"G. Kalai","year":"1997","unstructured":"G. Kalai. Linear programming, the simplex algorithm and simple polytopes. Math. Programming, 79:217\u2013233, 1997.","journal-title":"Math. Programming"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L. G. Khachiyan","year":"1980","unstructured":"L. G. Khachiyan. Polynomial algorithms in linear programming. U.S.S.R. Comput. Math. and Math. Phys, 20:53\u201372, 1980.","journal-title":"U.S.S.R. Comput. Math. and Math. Phys"},{"unstructured":"V. Klee and G. J. Minty. How good is the simplex algorithm? In O. Shisha, editor, Inequalities III, pages 159\u2013175. Academic Press, 1972.","key":"8_CR18"},{"key":"8_CR19","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J. Matou\u0161ek","year":"1996","unstructured":"J. Matou\u0161ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16:498\u2013516, 1996.","journal-title":"Algorithmica"},{"issue":"4","key":"8_CR20","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1002\/rsa.3240050408","volume":"5","author":"J. Matou\u0161ek","year":"1994","unstructured":"J. Matou\u0161ek. Lower bounds for a subexponential optimization algorithm. Random Structures & Algorithms, 5(4):591\u2013607, 1994.","journal-title":"Random Structures & Algorithms"},{"doi-asserted-by":"crossref","unstructured":"M. Sharir and E. Welzl. Rectilinear and polygonal p-piercing and p-center problems. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 122\u2013132, 1996.","key":"8_CR21","DOI":"10.1145\/237218.237255"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T19:46:02Z","timestamp":1556480762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}