{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T22:00:13Z","timestamp":1790805613916,"version":"4.1.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4-5","license":[{"start":{"date-parts":[[1996,10,1]],"date-time":"1996-10-01T00:00:00Z","timestamp":844128000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,10]]},"DOI":"10.1007\/bf01940877","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T06:46:47Z","timestamp":1122792407000},"page":"498-516","source":"Crossref","is-referenced-by-count":162,"title":["A subexponential bound for linear programming"],"prefix":"10.1007","volume":"16","author":[{"given":"J.","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"E.","family":"Welzl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01940877_CR1","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02574379","volume":"12","author":"N. Amenta","year":"1994","unstructured":"N. Amenta, Helly-type theorems and generalized linear programming,Discrete Comput. Geom.,12 (1994), 241\u2013261.","journal-title":"Discrete Comput. Geom."},{"key":"BF01940877_CR2","doi-asserted-by":"crossref","unstructured":"N. Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem,Proc. 10th Annual ACM Symposium on Computational Geometry, 1994, pp. 340\u2013347.","DOI":"10.1145\/177424.178064"},{"key":"BF01940877_CR3","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1002\/sapm1977562187","volume":"56","author":"D. E. Bell","year":"1977","unstructured":"D. E. Bell, A theorem concerning the integer lattice,Stud. Appl. Math.,56 (1977), 187\u2013188.","journal-title":"Stud. Appl. Math."},{"key":"BF01940877_CR4","unstructured":"B. Chazelle and J. Matou\u0161ek, On linear-time deterministic algorithms for optimization problems in fixed dimensions, Technical Report B 92-18, Dept. of Mathematics, Freie Universit\u00e4t Berlin (1992); alsoProc. 4th SIAM-ACM Symposium on Discrete Algorithms, 1993, pp. 281\u2013290."},{"key":"BF01940877_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(86)90037-2","volume":"22","author":"K. L. Clarkson","year":"1986","unstructured":"K. L. Clarkson, Linear programming inO(n \u00d7 3d 2) time,Inform. Process. Lett.,22 (1986), 21\u201324.","journal-title":"Inform. Process. Lett."},{"key":"BF01940877_CR6","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K. L. Clarkson, New applications of random sampling in computational geometry,Discrete Comput. Geom.,2 (1987), 195\u2013222.","journal-title":"Discrete Comput. Geom."},{"key":"BF01940877_CR7","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K. L. Clarkson","year":"1995","unstructured":"K. L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small,J. Assoc. Comput. Mach.,42 (1995), 488\u2013499.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01940877_CR8","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/BF01899996","volume":"8","author":"L. Danzer","year":"1957","unstructured":"L. Danzer, D. Laugwitz, and H. Lenz, \u00dcber das L\u00f6wnersche Ellipsoid und sein Analogon unter den einem Eik\u00f6rper eingeschriebenen Ellipsoiden,Arch. Math.,8 (1957), 214\u2013219.","journal-title":"Arch. Math."},{"key":"BF01940877_CR9","volume-title":"Linear Programming and Extensions","author":"D. B. Dantzig","year":"1963","unstructured":"D. B. Dantzig,Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963."},{"key":"BF01940877_CR10","unstructured":"J. D\u00f6rflinger, Approximation durch Kreise: Algorithmen zur Ermittlung der Formabweichung mit Koordinatenme\u00dfger\u00e4ten, Diplomarbeit, Universi\u00e4t Ulm, 1986."},{"key":"BF01940877_CR11","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1137\/0215052","volume":"15","author":"M. E. Dyer","year":"1986","unstructured":"M. E. Dyer, 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":"BF01940877_CR12","doi-asserted-by":"crossref","unstructured":"M. E. Dyer, A class of convex programs with applications to computational geometry,Proc. 8th Annual ACM Symposium on Computational Geometry, 1992, pp. 9\u201315.","DOI":"10.1145\/142675.142681"},{"key":"BF01940877_CR13","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01587088","volume":"44","author":"M. E. Dyer","year":"1989","unstructured":"M. E. Dyer and A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming,Math. Programming,44 (1989), 203\u2013212.","journal-title":"Math. Programming"},{"key":"BF01940877_CR14","unstructured":"B. G\u00e4rtner, personal communication (1991)."},{"key":"BF01940877_CR15","doi-asserted-by":"crossref","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 (1995), 1018\u20131035.","journal-title":"SIAM J. Comput."},{"key":"BF01940877_CR16","first-page":"143","volume":"30","author":"F. Juhnke","year":"1990","unstructured":"F. Juhnke, Volumenminimale Ellipsoid\u00fcberdeckungen,Beitr. Algebra Geom.,30 (1990), 143\u2013153.","journal-title":"Beitr. Algebra Geom."},{"key":"BF01940877_CR17","first-page":"241","volume":"123","author":"H. Jung","year":"1901","unstructured":"H. Jung, \u00dcber die kleinste Kugel, die eine r\u00e4umliche Figur einschlie\u00dft,J. Reine Angew. Math.,123 (1901), 241\u2013257.","journal-title":"J. Reine Angew. Math."},{"key":"BF01940877_CR18","doi-asserted-by":"crossref","unstructured":"G. Kalai, A subexponential randomized simplex algorithm,Proc. 24th ACM Symposium on Theory of Computing, 1992, pp. 475\u2013482.","DOI":"10.1145\/129712.129759"},{"key":"BF01940877_CR19","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica,4 (1984), 373\u2013395.","journal-title":"Combinatorica"},{"key":"BF01940877_CR20","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L. G. Khachiyan","year":"1980","unstructured":"L. G. Khachiyan, Polynomial algorithm in linear programming,U.S.S.R. Comput. Math. and Math. Phys.,20 (1980), 53\u201372.","journal-title":"U.S.S.R. Comput. Math. and Math. Phys."},{"key":"BF01940877_CR21","first-page":"159","volume-title":"Inequalities III","author":"V. Klee","year":"1972","unstructured":"V. Klee and G. J. Minty, How good is the simplex algorithm, inInequalities III, (O. Shisha, ed.), Academic Press, New York, 1972, pp. 159\u2013175."},{"key":"BF01940877_CR22","doi-asserted-by":"crossref","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 (1994), 591\u2013607.","journal-title":"Random Structures Algorithms"},{"key":"BF01940877_CR23","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, On geometric optimization with few violated constraints,Proc. 10th Annual ACM Symposium on Computational Geometry, 1994, pp. 312\u2013321.","DOI":"10.1145\/177424.178039"},{"key":"BF01940877_CR24","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, Linear time algorithms for linear time programming inR 3 and related problems,SIAM J. Comput.,12 (1983), 759\u2013776.","journal-title":"SIAM J. Comput."},{"key":"BF01940877_CR25","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"N. Megiddo, Linear programming in linear time when the dimension is fixed,J. Assoc. Comput. Mach.,31 (1984), 114\u2013127.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01940877_CR26","unstructured":"N. Megiddo, A note on subexponential simplex algorithms, manuscript (1992)."},{"key":"BF01940877_CR27","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF01949705","volume":"3","author":"J.-P. D'Oignon","year":"1973","unstructured":"J.-P. D'Oignon, Convexity in cristallographie lattices,J. Geom.,3 (1973), 71\u201385.","journal-title":"J. Geom."},{"key":"BF01940877_CR28","doi-asserted-by":"crossref","unstructured":"M. J. Post, Minimum spanning ellipsoids,Proc. 16th Annual ACM Symposium on Theory of Computing, 1984, pp. 108\u2013116.","DOI":"10.1145\/800057.808672"},{"key":"BF01940877_CR29","unstructured":"G. Rote, personal communication (1991)."},{"key":"BF01940877_CR30","doi-asserted-by":"crossref","first-page":"3637","DOI":"10.1073\/pnas.74.9.3637","volume":"74","author":"H. E. Scarf","year":"1977","unstructured":"H. E. Scarf, An observation on the structure of production sets with indivisibilities,Proc. Nat. Acad. Sci. U.S.A.,74 (1977), 3637\u20133641.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"BF01940877_CR31","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"R. Seidel, Low dimensional linear programming and convex hulls made easy,Discrete Comput. Geom.,6 (1991), 423\u2013434.","journal-title":"Discrete Comput. Geom."},{"key":"BF01940877_CR32","first-page":"569","volume-title":"Lecture Notes in Computer Science, 577","author":"M. Sharir","year":"1992","unstructured":"M. Sharir and E. Welzl, A combinatorial bound for linear programming and related problems,Proc. 9th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 577, Springer-Verlag, Berlin, 1992, pp. 569\u2013579."},{"key":"BF01940877_CR33","first-page":"79","volume":"1","author":"J. J. Sylvester","year":"1857","unstructured":"J. J. Sylvester, A question in the geometry of situation,Quart. J. Math.,1 (1857), 79.","journal-title":"Quart. J. Math."},{"key":"BF01940877_CR34","series-title":"Lecture Notes in Computer Science, Vol. 555","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BFb0038202","volume-title":"New Results and New Trends in Computer Science","author":"E. Welzl","year":"1991","unstructured":"E. Welzl, Smallest enclosing disks (balls and ellipsoids),New Results and New Trends in Computer Science (H. Maurer, ed.), Lecture Notes in Computer Science, Vol. 555, Springer-Verlag, Berlin, 1991, pp. 359\u2013370."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940877.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01940877\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T09:31:10Z","timestamp":1586338270000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01940877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":34,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["BF01940877"],"URL":"https:\/\/doi.org\/10.1007\/bf01940877","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}