{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:47:42Z","timestamp":1742939262034,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030174019"},{"type":"electronic","value":"9783030174026"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-17402-6_18","type":"book-chapter","created":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T13:37:00Z","timestamp":1558359420000},"page":"212-223","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Finding a Mediocre Player"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,6]]},"reference":[{"issue":"1","key":"18_CR1","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})$$. J. Comput. Syst. Sci. 38(1), 125\u2013133 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR2","unstructured":"Alexandrescu, A.: Fast deterministic selection. In: Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), June 2017, London, pp. 24:1\u201324:19 (2017)"},{"key":"18_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":"18_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, pp. 226\u2013238. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46521-9_19"},{"key":"18_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":"18_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. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-319-21840-3_16","volume-title":"Algorithms and Data Structures","author":"K Chen","year":"2015","unstructured":"Chen, K., Dumitrescu, A.: Select with groups of 3 or 4. In: Dehne, F., Sack, J.R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 189\u2013199. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_16. arXiv.org\/abs\/1409.3600"},{"key":"18_CR8","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"},{"issue":"2","key":"18_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. J. ACM 36(2), 270\u2013279 (1989)","journal-title":"J. ACM"},{"issue":"3","key":"18_CR10","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 J. Discrete Math. 14(3), 299\u2013311 (2001)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"18_CR11","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":"18_CR12","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 J. Comput. 28(5), 1722\u20131758 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"18_CR13","doi-asserted-by":"publisher","first-page":"58","DOI":"10.3390\/a12030058","volume":"12","author":"A Dumitrescu","year":"2019","unstructured":"Dumitrescu, A.: A selectable sloppy heap. Algorithms 12(3), 58 (2019). https:\/\/doi.org\/10.3390\/a12030058","journal-title":"Algorithms"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A.: Finding a mediocre player (2019, preprint). arXiv.org\/abs\/1901.09017","DOI":"10.1007\/978-3-030-17402-6_18"},{"key":"18_CR15","unstructured":"Edelkamp, S., Wei\u00df, A.: QuickMergesort: practically efficient constant-factor optimal sorting, preprint available at arXiv.org\/abs\/1804.10062"},{"issue":"3","key":"18_CR16","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. Commun. ACM 18(3), 165\u2013172 (1975)","journal-title":"Commun. ACM"},{"issue":"2","key":"18_CR17","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. J. ACM 26(2), 227\u2013238 (1979)","journal-title":"J. ACM"},{"key":"18_CR18","first-page":"585","volume":"4","author":"A Hadian","year":"1969","unstructured":"Hadian, A., Sobel, M.: Selecting the $$t$$-th largest using binary errorless comparisons. Comb. Theory Appl. 4, 585\u2013599 (1969)","journal-title":"Comb. Theory Appl."},{"issue":"7","key":"18_CR19","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). Commun. ACM 4(7), 321\u2013322 (1961)","journal-title":"Commun. ACM"},{"issue":"1","key":"18_CR20","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 J. Comput. 5(1), 109\u2013114 (1976)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"18_CR21","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 J. Comput. 17(4), 640\u2013647 (1988)","journal-title":"SIAM J. Comput."},{"key":"18_CR22","unstructured":"Kaplan, H., Kozma, L., Zamir, O., Zwick, U.: Selection from heaps, row-sorted matrices and X+Y using soft heaps (2018, preprint). http:\/\/arXiv.org\/abs\/1802.07041"},{"issue":"1","key":"18_CR23","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. J. ACM 28(1), 150\u2013165 (1981)","journal-title":"J. ACM"},{"key":"18_CR24","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edn. Addison-Wesley, Reading (1998)","edition":"2"},{"key":"18_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"18_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"18_CR27","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 \u2014 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). https:\/\/doi.org\/10.1007\/3-540-61422-2_146"},{"issue":"2","key":"18_CR28","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. J. Comput. Syst. Sci. 13(2), 184\u2013199 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR29","unstructured":"Yao, F.: On lower bounds for selection problems. Technical report MAC TR-121, Massachusetts Institute of Technology, Cambridge (1974)"},{"issue":"9","key":"18_CR30","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. Commun. ACM 19(9), 501\u2013508 (1976)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17402-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T12:56:37Z","timestamp":1710334597000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17402-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030174019","9783030174026"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17402-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"6 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"95","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"14","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}