{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:54:33Z","timestamp":1787504073631,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540614227","type":"print"},{"value":"9783540685296","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_146","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:37:08Z","timestamp":1330274228000},"page":"368-379","source":"Crossref","is-referenced-by-count":16,"title":["Progress in selection"],"prefix":"10.1007","author":[{"given":"Mike","family":"Paterson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"S. W. Bent and J. W. John. Finding the median requires 2n comparisons. In Proc. 17th ACM Symp. on Theory of Computing, 1985, 213\u2013216.","DOI":"10.1145\/22145.22169"},{"key":"32_CR2","doi-asserted-by":"crossref","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. Time bounds for selection. J. Comput. Syst. Sci., 7, 1973, 448\u2013461.","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(86)90026-9","volume":"61","author":"J. W. Daykin","year":"1986","unstructured":"J. W. Daykin. Inequalities for the number of monotonie functions of partial orders. Discrete Mathematics, 61, 1986, 41\u201355.","journal-title":"Discrete Mathematics"},{"key":"32_CR4","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(84)90049-9","volume":"50","author":"D. E. Daykin","year":"1984","unstructured":"D. E. Daykin, J. W. Daykin, and M. S. Paterson. On log concavity for order-preserving maps of partial orders. Discrete Mathematics, 50, 1984, 221\u2013226.","journal-title":"Discrete Mathematics"},{"key":"32_CR5","unstructured":"D. Dor. Selection Algorithms. PhD thesis, Tel-Aviv University, 1995."},{"key":"32_CR6","unstructured":"D. Dor and U. Zwick. Selecting the median. In Proc. 6th Annual ACM-SIAM Symp. on Discrete Algorithms, 1995, 28\u201337."},{"key":"32_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01300126","volume":"16","author":"D. Dor","year":"1996","unstructured":"D. Dor and U. Zwick. Finding the \u03b1n th largest element. Combinatorica, 16, 1996, 41\u201358.","journal-title":"Combinatorica"},{"key":"32_CR8","unstructured":"D. Dor and U. Zwick. Median selection requires (2+\u03b5)n comparisons. Technical Report 312\/96, April 1996, Department of Computer Science, Tel Aviv University."},{"key":"32_CR9","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1145\/322123.322128","volume":"26","author":"F. Fussenegger","year":"1978","unstructured":"F. Fussenegger and H. N. Gabow. A counting approach to lower bounds for selection problems. J. ACM, 26, 1978, 227\u2013238.","journal-title":"J. ACM"},{"key":"32_CR10","first-page":"585","volume":"4","author":"A. Hadian","year":"1969","unstructured":"A. Hadian and M. Sobel. Selecting the t th largest using binary errorless comparisons. Colloquia Mathematica Societatis J\u00e1nos Bolyai, 4, 1969, 585\u2013599.","journal-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai"},{"key":"32_CR11","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1137\/0205010","volume":"5","author":"L. Hyafil","year":"1976","unstructured":"L. Hyafil. Bounds for selection. SIAM J. on Computing, 5, 1976, 109\u2013114.","journal-title":"SIAM J. on Computing"},{"key":"32_CR12","volume-title":"PhD thesis","author":"J. W. John","year":"1985","unstructured":"J. W. John. The Complexity of Selection Problems. PhD thesis, University of Wisconsin at Madison, 1985."},{"key":"32_CR13","unstructured":"D. G. Kirkpatrick. Topics in the complexity of combinatorial algorithms. Tech. Rep. 74, Dept. of Computer Science, University of Toronto, 1974."},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1145\/322234.322245","volume":"28","author":"D. G. Kirkpatrick","year":"1981","unstructured":"D. G. Kirkpatrick. A unified lower bound for selection and set partitioning problems. J. ACM, 28, 1981, 150\u2013165.","journal-title":"J. ACM"},{"key":"32_CR15","first-page":"557","volume":"5","author":"S. S. Kislitsyn","year":"1964","unstructured":"S. S. Kislitsyn. On the selection of the k th element of an ordered set by pairwise comparisons. Sibirsk. Mat. Zh., 5, 1964, 557\u2013564. (In Russian.)","journal-title":"Sibirsk. Mat. Zh."},{"key":"32_CR16","volume-title":"Sorting and Searching, volume 3 of The Art of Computer Programming","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973."},{"key":"32_CR17","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0020-0190(82)90120-X","volume":"15","author":"T. Motoki","year":"1982","unstructured":"T. Motoki. A note on upper bounds for the selection problem. Inf. Proc. Lett., 15, 1982, 214\u2013219.","journal-title":"Inf. Proc. Lett."},{"key":"32_CR18","unstructured":"J. I. Munro and P. V. Poblete. A lower bound for determining the median. Technical Report Research Report CS-82-21, University of Waterloo, 1982."},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"V. Pratt and F. F. Yao. On lower bounds for computing the i th largest element. In Proc. 14th IEEE Symp. on Switching and Automata Theory, 1973, 70\u201381.","DOI":"10.1109\/SWAT.1973.18"},{"key":"32_CR20","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/0196-6774(84)90008-7","volume":"5","author":"P. V. Ramanan","year":"1984","unstructured":"P. V. Ramanan and L. Hyafil. New algorithms for selection. J. Algorithms, 5, 1984, 557\u2013578.","journal-title":"J. Algorithms"},{"key":"32_CR21","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A. Sch\u00f6nhage","year":"1976","unstructured":"A. Sch\u00f6nhage, M. S. Paterson, and N. Pippenger. Finding the median. J. Comput. Syst. Sci., 13, 1976, 184\u2013199.","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR22","first-page":"154","volume":"7","author":"J. Schreier","year":"1932","unstructured":"J. Schreier. On tournament elimination systems. Mathesis Polska, 7, 1932, 154\u2013160. (In Polish.)","journal-title":"Mathesis Polska"},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"F. F. Yao. On lower bounds for selection problems. Technical Report MAC TR-121, M.I.T., 1974.","DOI":"10.1109\/SWAT.1974.6"},{"key":"32_CR24","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/360336.360339","volume":"19","author":"C. K. Yap","year":"1976","unstructured":"C. K. Yap. New upper bounds for selection. Comm. ACM, 19, 1976, 501\u2013508.","journal-title":"Comm. ACM"},{"key":"32_CR25","unstructured":"C. K. Yap. New lower bounds for medians and related problems. Computer Science Report 79, Yale University, 1976."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_146.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:06:05Z","timestamp":1605629165000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_146","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}