{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:18Z","timestamp":1725664518640},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_54","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:55Z","timestamp":1330290295000},"page":"667-687","source":"Crossref","is-referenced-by-count":8,"title":["Linear programming \u2014 Randomization and abstract frameworks"],"prefix":"10.1007","author":[{"given":"Bernd","family":"G\u00e4rtner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emo","family":"Welzl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF01582137","volume":"61","author":"I. Adler","year":"1993","unstructured":"Adler, I. and Shamir, R.: A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio. Math. Programming 61 (1993) 39\u201352","journal-title":"Math. Programming"},{"key":"54_CR2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02574379","volume":"12","author":"N. Amenta","year":"1994","unstructured":"Amenta, N.: Helly-type theorems and generalized linear programming. Discrete Comput. Geom. 12 (1994) 241\u2013261","journal-title":"Discrete Comput. Geom."},{"key":"54_CR3","unstructured":"Amenta, N.: Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem. Proc. 10th Annu. ACM Symp. Computational Geometry (1994) 340\u2013347"},{"key":"54_CR4","volume-title":"Volume 1 of Algorithms and Combinatorics","author":"K. H. Borgwardt","year":"1987","unstructured":"Borgwardt, K. H.: The Simplex Method. A Probabilistic Analysis. Volume 1 of Algorithms and Combinatorics, Springer-Verlag, Berlin-Heidelberg (1987)"},{"key":"54_CR5","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimensions. Proc. 4th SIAM-ACM Symp. on Discrete Alg. (1993) 281\u2013290"},{"key":"54_CR6","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear Programming. W. H. Freeman, New York, NY (1983)."},{"key":"54_CR7","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(86)90037-2","volume":"22","author":"K. L. Clarkson","year":"1986","unstructured":"Clarkson, K. L.: Linear programming in $$O(n3^{d^2 } )$$ time. Inform. Process. Lett. 22 (1986) 21\u201324","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"54_CR8","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L.: A Las Vegas algorithm for linear and integer programming when the dimension is small. J. ACM 42(2) (1995) 488\u2013499","journal-title":"J. ACM"},{"key":"54_CR9","volume-title":"Linear Programming and Extensions","author":"G. B. Dantzig","year":"1963","unstructured":"Dantzig, G. B.: Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963)."},{"key":"54_CR10","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF01900144","volume":"8","author":"Danzer","year":"1957","unstructured":"Danzer, \u00dcber ein Problem aus der kombinatorischen Geometrie. Arch. Math. 8 (1957) 347\u2013351","journal-title":"Arch. Math."},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M. E. Dyer","year":"1984","unstructured":"Dyer, M. E.: Linear algorithms for two and three-variable linear programs. SIAM J. Comput. 13 (1984) 31\u201345.","journal-title":"SIAM J. Comput."},{"key":"54_CR12","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1137\/0215052","volume":"15","author":"M. E. Dyer","year":"1986","unstructured":"Dyer, M. E.: On a multidimensional search technique and its application to the Euclidean one-center problem. SIAM J. Comput. 15 (1986) 725\u2013738","journal-title":"SIAM J. Comput."},{"key":"54_CR13","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01587088","volume":"44","author":"M. E. Dyer","year":"1989","unstructured":"Dyer, M. E., Frieze, A. M., A randomized algorithm for fixed-dimensional linear programming. Math. Programming 44 (1989) 203\u2013212","journal-title":"Math. Programming"},{"key":"54_CR14","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1137\/S0097539793250287","volume":"24","author":"B. G\u00e4rtner","year":"1995","unstructured":"G\u00e4rtner, B.: A subexponential algorithm for abstract optimization problems. SIAM J. Comput. 24 (1995) 1018\u20131035","journal-title":"SIAM J. Comput."},{"key":"54_CR15","unstructured":"G\u00e4rtner, B.: Randomized Optimization by Simplex-Type Methods. PhD thesis, Institute for Computer Science, Free University Berlin (1995)"},{"issue":"2","key":"54_CR16","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/202840.202847","volume":"26","author":"M. Goldwasser","year":"1995","unstructured":"Goldwasser, M.: A survey of linear programming in randomized subexponential time. ACM-SIGACT News 26(2) (1995) 96\u2013104","journal-title":"ACM-SIGACT News"},{"key":"54_CR17","unstructured":"Kalai, G.: A subexponential randomized simplex algorithm. Proc. 24th Annu. ACM Symp. Theory of Computing (1992) 475\u2013482"},{"key":"54_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L. G. Khachiyan","year":"1980","unstructured":"Khachiyan, L. G.: Polynomial algorithms in linear programming. US.S.R. Comput. Math. and Math. Phys. 20 (1980) 53\u201372","journal-title":"US.S.R. Comput. Math. and Math. Phys."},{"key":"54_CR19","unstructured":"Klee, V., Minty, G. J.: How good is the simplex algorithm? In O. Shisha, editor, Inequalities III, Academic Press (1972) 159\u2013175"},{"key":"54_CR20","unstructured":"Matou\u0161ek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Proc. 8th Annu. ACM Symp. Computational Geometry (1992) 1\u20138; Algorithmica, to appear"},{"issue":"4","key":"54_CR21","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1002\/rsa.3240050408","volume":"5","author":"J. Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J.: Lower bounds for a subexponential optimization algorithm. Random Structures & Algorithms 5(4) (1994) 591\u2013607","journal-title":"Random Structures & Algorithms"},{"key":"54_CR22","unstructured":"Matou\u0161ek, J.: On geometric optimization with few violated constraints. Proc. 10th Annu. ACM Symp. Computational Geometry (1994) 312\u2013321"},{"key":"54_CR23","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31 (1984) 114\u2013127","journal-title":"J. ACM"},{"key":"54_CR24","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"Seidel, R.: Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom. 6 (1991) 423\u2013434","journal-title":"Discrete Comput. Geom."},{"key":"54_CR25","volume-title":"Theory of Linear and Integer Programming","author":"A. Shrijver","year":"1986","unstructured":"Shrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"key":"54_CR26","first-page":"569","volume":"577","author":"M. Sharir","year":"1992","unstructured":"Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. Proc. 9th Symp. Theo. Asp. Comp. Sci., Lecture Notes in Computer Science 577 (1992) 569\u2013579","journal-title":"Proc. 9th Symp. Theo. Asp. Comp. Sci., Lecture Notes in Computer Science"},{"key":"54_CR27","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: Rectilinear and polygonal p-piercing and p-center problems. Manuscript, submitted (1995)","DOI":"10.1145\/237218.237255"},{"key":"54_CR28","unstructured":"Sharir, M., Welzl, E.: Circular and spherical separability. Manuscript, submitted (1995)"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:02:39Z","timestamp":1605646959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}