{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:36:11Z","timestamp":1742402171378},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671596"},{"type":"electronic","value":"9783540465218"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46521-9_19","type":"book-chapter","created":{"date-parts":[[2007,11,3]],"date-time":"2007-11-03T22:47:16Z","timestamp":1194130036000},"page":"226-238","source":"Crossref","is-referenced-by-count":18,"title":["An Efficient Algorithm for the Approximate Median Selection Problem"],"prefix":"10.1007","author":[{"given":"Sebastiano","family":"Battiato","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domenico","family":"Cantone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dario","family":"Catalano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianluca","family":"Cincotti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Hofri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,2,14]]},"reference":[{"key":"19_CR1","volume-title":"The Design and Analysis of Computeralgorithms","author":"A.V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computeralgorithms. Addison Wesley, Reading, MA 1974."},{"key":"19_CR2","volume-title":"Fundamentals of Algorithmics","author":"G. Brassard","year":"1996","unstructured":"G. Brassard and P. Bratley. Fundamentals of Algorithmics. Prentice-Hall, Englewood Cliffs, NJ 1996."},{"key":"19_CR3","unstructured":"S. Battiato, D. Cantone, D. Catalano, G. Cincotti, and M. Hofri. An Efficient Algorithm for the Approximate Median Selection Problem. Technical Report WPICS-TR-99-26, Worcester Polytechnic Institute, October 1999. Available from http:\/ftp:\/\/ftp.cs.wpi.edu\/pub\/techreports\/99-26.ps.gz."},{"issue":"4","key":"19_CR4","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. Pratt, R.L. Rivest, and R. Tarjan. Time bounds for selection. Journal of Computer and Systems Sciences, 7(4):448\u2013461, 1973.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"19_CR5","unstructured":"S. Carlsson, M. Sundstrom. Linear-time In-place Selection in Less than 3n Comparisons-Division of Computer Science, Lulea University of Technology, S-971 87 LULEA, Sweden."},{"key":"19_CR6","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990."},{"issue":"2","key":"19_CR7","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1145\/62044.62047","volume":"36","author":"W. Cunto","year":"1989","unstructured":"W. Cunto and J.I. Munro. Average case selection. Journal of the ACM, 36(2):270\u2013279, 1989.","journal-title":"Journal of the ACM"},{"key":"19_CR8","unstructured":"Alvin W. Drake. Fundamentals of Applied Probability Theory. McGraw-Hill, 1967."},{"issue":"5","key":"19_CR9","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1137\/S0097539795288611","volume":"28","author":"D. Dor","year":"1999","unstructured":"D. Dor, and U. Zwick. Selecting the Median. SIAM Jour. Comp., 28(5):1722\u20131758, 1999.","journal-title":"SIAM Jour. Comp."},{"key":"19_CR10","first-page":"420","volume":"12","author":"G.N. Frederickson","year":"1980","unstructured":"G.N. Frederickson, D.B. Johnson. Generalized Selection and Ranking. Proceedings STOC-SIGACT, Los Angeles CA, 12:420\u2013428, 1980.","journal-title":"Proceedings STOC-SIGACT"},{"key":"19_CR11","first-page":"26","volume":"22","author":"G.N. Frederickson","year":"1990","unstructured":"G.N. Frederickson. The Information Theory Bound is Tight for selection in a heap. Proceedings STOC-SIGACT, Baltimore MD, 22:26\u201333, 1990.","journal-title":"Proceedings STOC-SIGACT"},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1145\/360680.360691","volume":"18","author":"R.W. Floyd","year":"1975","unstructured":"R.W. Floyd, R.L. Rivest. Expected time bounds for selection. Communications of the ACM, 18(3):165\u2013172, 1975.","journal-title":"Communications of the ACM"},{"issue":"7","key":"19_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"C.A.R. Hoare. Algorithm 63(partition) and algorithm 65(find). Communications of the ACM, 4(7):321\u2013322, 1961.","journal-title":"Communications of the ACM"},{"key":"19_CR14","volume-title":"Analysis of Algorithms: Computational Methods & Mathematical Tools","author":"M. Hofri","year":"1995","unstructured":"M. Hofri, Analysis of Algorithms: Computational Methods & Mathematical Tools, Oxford University Press, New York (1995)."},{"key":"19_CR15","first-page":"311","volume":"10","author":"C. Hurley","year":"1995","unstructured":"C. Hurley and Reza Modarres: Low-Storage quantile estimation, Computational Statistics, 10:311\u2013325, 1995.","journal-title":"Computational Statistics"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<143::AID-RSA7>3.0.CO;2-V","volume":"10","author":"P. Kirschenhofer","year":"1997","unstructured":"P. Kirschenhofer, C. Martinez, and H. Prodinger. Analysis of Hoare\u2019s Find algorithm with median-of-three partition. Random Structures and Algorithms, 10:143\u2013156, 1997.","journal-title":"Random Structures and Algorithms"},{"key":"19_CR17","unstructured":"J. Katajainen. The Ultimate Heapsort, DIKU Report 96\/42, Department of Computer Science, Univ. of Copenhagen, 1996."},{"key":"19_CR18","unstructured":"D.E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 2nd Ed. 1999."},{"key":"19_CR19","series-title":"Lect Notes Comput Sci","first-page":"18","volume-title":"Scandinavian Workshop on Algorithm Theory(SWAT88","author":"T.W. Lai","year":"1988","unstructured":"T.W. Lai, and D. Wood. Implicit Selection. Scandinavian Workshop on Algorithm Theory(SWAT88):18\u201323, LNCS 38Springer-Verlag, 1988."},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Sorting and Searching, Data Structures and Algorithms, volume 1. Springer-Verlag, 1984.","DOI":"10.1007\/978-3-642-69672-5_2"},{"issue":"5","key":"19_CR21","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1016\/S0022-0000(73)80038-8","volume":"7","author":"A. Nozaky","year":"1973","unstructured":"A. Nozaky. Two Entropies of a Generalized Sorting Problems. Journal of Computer and Systems Sciences, 7(5):615\u2013621, 1973.","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"10","key":"19_CR22","doi-asserted-by":"publisher","first-page":"1192","DOI":"10.1145\/63039.63042","volume":"31","author":"S. K. Park","year":"1988","unstructured":"S. K. Park and K. W. Miller. Random number generators: good ones are hard to find. Communications of the ACM, 31(10):1192\u20131201, 1988. Updated in Communications of the ACM, 36(7):108-110, 1993.","journal-title":"Communications of the ACM"},{"key":"19_CR23","volume-title":"Technical Report N.1115","author":"L. Rosaz","year":"1997","unstructured":"L. Rosaz. Improving Katajainen\u2019s Ultimate Heapsort, Technical Report N.1115, Laboratoire de Recherche en Informatique, Universit'e de Paris Sud, Orsay, 1997."},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"97","DOI":"10.2307\/2289530","volume":"409","author":"P.J. Rousseeuw","year":"1990","unstructured":"P.J. Rousseeuw and G.W. Bassett: The remedian: A robust averaging method for large data sets. Jour. Amer. Statist. Assoc, 409:97\u2013104, 1990.","journal-title":"Jour. Amer. Statist. Assoc"},{"key":"19_CR25","unstructured":"Savante Janson-Private communication, June 1999."},{"key":"19_CR26","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A. Schonhage","year":"1976","unstructured":"A. Schonhage, M. Paterson, and N. Pippenger. Finding the median. Journal of Computer and Systems Sciences, 13:184\u2013199, 1976.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"19_CR27","unstructured":"B. W. Weide. Space efficient on-line selection algorithm. Proceedings of the 11th symposium of Computer Science and Statistics, on the interface, 308\u2013311. (1978)."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46521-9_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T04:44:39Z","timestamp":1556945079000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46521-9_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671596","9783540465218"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-46521-9_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}