{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:21:59Z","timestamp":1743056519191,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054365","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"169-180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Two-variable linear programming in parallel"],"prefix":"10.1007","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"issue":"6","key":"16_CR1","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/S0097539792234858","volume":"25","author":"M. Ajtai","year":"1996","unstructured":"M. Ajtai and N. Megiddo, \u201cA deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension,\u201d SIAM J. Comput., 25 (6) (1996), pp. 1171\u20131195.","journal-title":"SIAM J. Comput."},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon and N. Megiddo, \u201cParallel linear programming in fixed dimension almost surely in constant time,\u201d Proc. 31st Annual IEEE Symp. on Foundation of Computer Science, 1990, pp. 574\u2013582.","DOI":"10.1109\/FSCS.1990.89578"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"M. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest, and R.E. Tarjan, \u201cTime bounds for selection,\u201d Journal of Computer and System Sciences, 7 (1973), pp. 448\u2013461.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"R.P. Brent, \u201cThe parallel evaluation of general arithmetic expressions,\u201d Journal of the ACM, 21 (1974), pp. 201\u2013206.","journal-title":"Journal of the ACM"},{"key":"16_CR5","unstructured":"B. Chazelle and J. Matou\u0161ek, \u201cOn linear-time deterministic algorithms for optimization problems in fixed dimension,\u201d Proc. 4th Annual ACM-SIAM Symp. on Discrete Algorithms, 1993, pp. 281\u2013290."},{"issue":"1","key":"16_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1109\/71.363412","volume":"6","author":"D.Z. Chen","year":"1995","unstructured":"D.Z. Chen, \u201cEfficient geometric algorithms on the EREW PRAM,\u201d IEEE Trans. on Parallel and Distributed Systems, 6 (1) (1995), pp. 41\u201347.","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"D.Z. Chen, W. Chen, K. Wada, and K. Kawaguchi, \u201cParallel algorithms for partitioning sorted sets and related problems,\u201d Proc. of 4th Annual European Symp. on Algorithms, 1996, pp. 234\u2013245.","DOI":"10.1007\/3-540-61680-2_59"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(86)90037-2","volume":"22","author":"K.L. Clarkson","year":"1986","unstructured":"K.L. Clarkson, \u201cLinear programming in $$O(n3^{d^2 } )$$ time,\u201d Information Processing Letters, 22 (1986), pp. 21\u201324.","journal-title":"Information Processing Letters"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"K.L. Clarkson, \u201cA Las Vegas algorithm for linear programming when the dimension is small,\u201d J. of the ACM, 42 (1995), pp. 488\u2013499.","journal-title":"J. of the ACM"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0020-0190(88)90186-X","volume":"26","author":"R. J. Cole","year":"1987\/1988","unstructured":"R. J. Cole, \u201cAn optimally efficient selection algorithm,\u201d Information Processing Letters, 26 (1987\/1988), pp. 295\u2013299.","journal-title":"Information Processing Letters"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R.J. Cole","year":"1988","unstructured":"R.J. Cole, \u201cParallel merge sort,\u201d SIAM J. Computing, 17 (1988), pp. 770\u2013785.","journal-title":"SIAM J. Computing"},{"key":"16_CR12","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 1990."},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0020-0190(90)90026-T","volume":"35","author":"X. Deng","year":"1990","unstructured":"X. Deng, \u201cAn optimal parallel algorithm for linear programming in the plane,\u201d Information Processing Letters, 35 (1990), pp. 213\u2013217.","journal-title":"Information Processing Letters"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M.E. Dyer","year":"1984","unstructured":"M.E. Dyer, \u201cLinear time algorithms for two-and three-variable linear programs,\u201d SIAM J. Computing, 13 (1984), pp. 31\u201345.","journal-title":"SIAM J. Computing"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1137\/0215052","volume":"15","author":"M.E. Dyer","year":"1986","unstructured":"M.E. Dyer, \u201cOn a multidimensional search technique and its applications to the Euclidean one-center problem,\u201d SIAM J. Computing, 15 (1986), pp. 725\u2013738.","journal-title":"SIAM J. Computing"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"M.E. Dyer, \u201cA parallel algorithm for linear programming in fixed dimension,\u201d Proc. 11th Annual Symp. on Computational Geometry, 1995, pp. 345\u2013349.","DOI":"10.1145\/220279.220316"},{"key":"16_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987."},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, \u201cGeometric partitioning made easier, even in parallel,\u201d Proc. 9th Annual ACM Symp. on Computational Geometry., 1993, pp. 73\u201382.","DOI":"10.1145\/160985.161002"},{"key":"16_CR19","unstructured":"M.T. Goodrich, \u201cFixed-dimensional parallel linear programming via relative epsilon-approximations,\u201d Proc. 7th Annual ACM-SIAM Symp. on Discrete Algorithms, 1996, pp. 132\u2013141."},{"key":"16_CR20","unstructured":"M.T. Goodrich and E.A. Ramos, \u201cBounded-independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming,\u201d to appear in Discrete & Computational Geometry."},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"T. Hayashi, K. Nakano, and S. Olariu, \u201cWeighted and unweighted selection algorithms for k sorted sequences,\u201d Proc. 8th International Symp. on Algorithms and Computation, 1997, pp. 52\u201361.","DOI":"10.1007\/3-540-63890-3_7"},{"key":"16_CR22","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J. J\u00e1J\u00e1, An Introduction to Parallel Algorithms, Addison-Wesley, Reading, Massachusetts, 1992."},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"G. Kalai, \u201cA subexponential randomized simplex algorithm,\u201d Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, pp. 475\u2013482.","DOI":"10.1145\/129712.129759"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J. Matou\u0161ek","year":"1996","unstructured":"J. Matou\u0161ek, M. Sharir, and E. Welzl, \u201cA subexponential bound for linear programming,\u201d Algorithmica, 16 (1996), pp. 498\u2013516.","journal-title":"Algorithmica"},{"issue":"4","key":"16_CR25","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, \u201cLinear time algorithms for linear programming in R3 and related problems,\u201d SIAM J. Computing, 12 (4) (1983), pp. 759\u2013776.","journal-title":"SIAM J. Computing"},{"issue":"1","key":"16_CR26","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"N. Megiddo, \u201cLinear programming in linear time when the dimension is fixed,\u201d Journal of ACM, 31 (1) (1984), pp. 114\u2013127.","journal-title":"Journal of ACM"},{"key":"16_CR27","unstructured":"C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982."},{"key":"16_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, Berlin, 1985."},{"key":"16_CR29","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"R. Seidel, \u201cSmall-dimensional linear programming and convex hulls made easy,\u201d Discrete & Computational Geometry, 6 (1991), pp. 423\u2013434.","journal-title":"Discrete & Computational Geometry"},{"key":"16_CR30","unstructured":"S. Sen, \u201cA deterministic poly(log log n) time optimal CRCW PRAM algorithm for linear programming in fixed dimension,\u201d Technical Report 95-08, Dept. of Computer Science, University of Newcastle, 1995."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054365","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:20:55Z","timestamp":1736407255000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/bfb0054365","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}