{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T11:35:39Z","timestamp":1742988939449,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_16","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"189-199","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Select with Groups of 3 or 4"],"prefix":"10.1007","author":[{"given":"Ke","family":"Chen","sequence":"first","affiliation":[]},{"given":"Adrian","family":"Dumitrescu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"16_CR1","volume-title":"Data Structures and Algorithms","author":"AV Aho","year":"1983","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data Structures and Algorithms. Addison-Wesley, Reading (1983)"},{"issue":"1","key":"16_CR2","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0022-0000(89)90035-4","volume":"38","author":"M Ajtai","year":"1989","unstructured":"Ajtai, M., Koml\u00f3s, J., Steiger, W.L., Szemer\u00e9di, E.: Optimal parallel selection has complexity $$O(\\log \\log {n})$$. Journal of Computer and System Sciences 38(1), 125\u2013133 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR3","volume-title":"Computer Algorithms: Introduction to Design and Analysis","author":"S Baase","year":"1988","unstructured":"Baase, S.: Computer Algorithms: Introduction to Design and Analysis, 2nd edn. Addison-Wesley, Reading (1988)","edition":"2"},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/3-540-46521-9_19","volume-title":"Algorithms and Complexity","author":"S Battiato","year":"2000","unstructured":"Battiato, S., Cantone, D., Catalano, D., Cincotti, G., Hofri, M.: An efficient algorithm for the approximate median selection problem. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, p. 226. Springer, Heidelberg (2000)"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Bent, S.W., John, J.W.: Finding the median requires $$2n$$ comparisons. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC 1985), pp. 213\u2013216. ACM (1985)","DOI":"10.1145\/22145.22169"},{"issue":"4","key":"16_CR6","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences 7(4), 448\u2013461 (1973)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR7","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"16_CR8","volume-title":"Instructor\u2019s Manual, to accompany Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Lee, C., Lin, E.: Instructor\u2019s Manual, to accompany Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"2","key":"16_CR9","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1145\/62044.62047","volume":"36","author":"W Cunto","year":"1989","unstructured":"Cunto, W., Munro, J.I.: Average case selection. Journal of ACM 36(2), 270\u2013279 (1989)","journal-title":"Journal of ACM"},{"key":"16_CR10","volume-title":"Algorithms","author":"S Dasgupta","year":"2008","unstructured":"Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms. Mc Graw Hill, New York (2008)"},{"issue":"3","key":"16_CR11","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/S0895480196309481","volume":"14","author":"D Dor","year":"2001","unstructured":"Dor, D., H\u00e5stad, J., Ulfberg, S., Zwick, U.: On lower bounds for selecting the median. SIAM Journal on Discrete Mathematics 14(3), 299\u2013311 (2001)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"16_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01300126","volume":"16","author":"D Dor","year":"1996","unstructured":"Dor, D., Zwick, U.: Finding the $$\\alpha n$$th largest element. Combinatorica 16(1), 41\u201358 (1996)","journal-title":"Combinatorica"},{"issue":"5","key":"16_CR13","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1137\/S0097539795288611","volume":"28","author":"D Dor","year":"1999","unstructured":"Dor, D., Zwick, U.: Selecting the median. SIAM Journal on Computing 28(5), 1722\u20131758 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1145\/360680.360691","volume":"18","author":"RW Floyd","year":"1975","unstructured":"Floyd, R.W., Rivest, R.L.: Expected time bounds for selection. Communications of ACM 18(3), 165\u2013172 (1975)","journal-title":"Communications of ACM"},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1145\/322123.322128","volume":"26","author":"F Fussenegger","year":"1979","unstructured":"Fussenegger, F., Gabow, H.N.: A counting approach to lower bounds for selection problems. Journal of ACM 26(2), 227\u2013238 (1979)","journal-title":"Journal of ACM"},{"key":"16_CR16","first-page":"585","volume":"4","author":"A Hadian","year":"1969","unstructured":"Hadian, A., Sobel, M.: Selecting the $$t$$-th largest using binary errorless comparisons. Combinatorial Theory and Its Applications 4, 585\u2013599 (1969)","journal-title":"Combinatorial Theory and Its Applications"},{"issue":"7","key":"16_CR17","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 63 (PARTITION) and algorithm 65 (FIND). Communications of the ACM 4(7), 321\u2013322 (1961)","journal-title":"Communications of the ACM"},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1137\/0205010","volume":"5","author":"L Hyafil","year":"1976","unstructured":"Hyafil, L.: Bounds for selection. SIAM Journal on Computing 5(1), 109\u2013114 (1976)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"16_CR19","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1137\/0217040","volume":"17","author":"JW John","year":"1988","unstructured":"John, J.W.: A new lower bound for the set-partitioning problem. SIAM Journal on Computing 17(4), 640\u2013647 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"16_CR20","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1145\/322234.322245","volume":"28","author":"DG Kirkpatrick","year":"1981","unstructured":"Kirkpatrick, D.G.: A unified lower bound for selection and set partitioning problems. Journal of ACM 28(1), 150\u2013165 (1981)","journal-title":"Journal of ACM"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-40273-9_6","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"D Kirkpatrick","year":"2013","unstructured":"Kirkpatrick, D.: Closing a long-standing complexity gap for selection: $$V_{3}$$(42) = 50. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 61\u201376. Springer, Heidelberg (2013)"},{"key":"16_CR22","volume-title":"Algorithm Design","author":"J Kleinberg","year":"2006","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design. Pearson & Addison-Wesley, Boston (2006)"},{"key":"16_CR23","series-title":"Sorting and Searching","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol. 3, 2nd edn. Addison-Wesley, Reading (1998)","edition":"2"},{"issue":"3","key":"16_CR24","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0196-6774(85)90011-2","volume":"6","author":"N Megiddo","year":"1985","unstructured":"Megiddo, N.: Partitioning with two lines in the plane. Journal of Algorithms 6(3), 430\u2013433 (1985)","journal-title":"Journal of Algorithms"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005)","DOI":"10.1017\/CBO9780511813603"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/3-540-61422-2_146","volume-title":"Algorithm Theory - SWAT \u201996","author":"M Paterson","year":"1996","unstructured":"Paterson, M.: Progress in selection. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 368\u2013379. Springer, Heidelberg (1996)"},{"issue":"2","key":"16_CR27","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A Sch\u00f6nhage","year":"1976","unstructured":"Sch\u00f6nhage, A., Paterson, M., Pippenger, N.: Finding the median. Journal of Computer and System Sciences 13(2), 184\u2013199 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"16_CR28","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1137\/0211034","volume":"11","author":"A Yao","year":"1982","unstructured":"Yao, A., Yao, F.: On the average-case complexity of selecting the $$k$$th best. SIAM Journal on Computing 11(3), 428\u2013447 (1982)","journal-title":"SIAM Journal on Computing"},{"issue":"9","key":"16_CR29","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/360336.360339","volume":"19","author":"CK Yap","year":"1976","unstructured":"Yap, C.K.: New upper bounds for selection. Communications of the ACM 19(9), 501\u2013508 (1976)","journal-title":"Communications of the ACM"},{"key":"16_CR30","unstructured":"Zwick, U.: Personal communication, September 2014"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T17:35:31Z","timestamp":1675272931000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}