{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:29:45Z","timestamp":1725506985880},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_5","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"48-59","source":"Crossref","is-referenced-by-count":8,"title":["Sorting and Selection with Random Costs"],"prefix":"10.1007","author":[{"given":"Stanislav","family":"Angelov","sequence":"first","affiliation":[]},{"given":"Keshav","family":"Kunal","sequence":"additional","affiliation":[]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","unstructured":"Alon, N., Blum, M., Fiat, A., Kannan, S., Naor, M., Ostrovsky, R.: Matching nuts and bolts. In: SODA, pp. 690\u2013696 (1994)"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1214\/aoap\/1177005202","volume":"4","author":"N. Alon","year":"1994","unstructured":"Alon, N., Bollob\u00e1s, B., Brightwell, G., Janson, S.: Linear extensions of a random partial order. Annals of Applied Probability\u00a04, 108\u2013123 (1994)","journal-title":"Annals of Applied Probability"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Brightwell, G.: Models of random partial orders, pp. 53\u201383 (1993)","DOI":"10.1017\/CBO9780511662089.004"},{"issue":"4","key":"5_CR4","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1006\/jcss.2002.1828","volume":"64","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J.M., Raghavan, P., Sahai, A.: Query strategies for priced information. J. Comput. Syst. Sci.\u00a064(4), 785\u2013819 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1145\/1060590.1060691","volume-title":"STOC","author":"F. Cicalese","year":"2005","unstructured":"Cicalese, F., Laber, E.S.: A new strategy for querying priced information. In: Gabow, H.N., Fagin, R. (eds.) STOC, pp. 674\u2013683. ACM, New York (2005)"},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1007\/11561071_59","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Cicalese","year":"2005","unstructured":"Cicalese, F., Laber, E.S.: An optimal algorithm for querying priced information: Monotone boolean functions and game trees. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 664\u2013676. Springer, Heidelberg (2005)"},{"key":"5_CR7","unstructured":"Daskalakis, C., Karp, R.M., Mossel, E., Riesenfeld, S., Verbin, E.: Sorting and Selection in Posets (2007), http:\/\/arxiv.org\/abs\/0707.1532"},{"key":"5_CR8","first-page":"375","volume-title":"STOC","author":"M.E. Dyer","year":"1989","unstructured":"Dyer, M.E., Frieze, A.M., Kannan, R.: A random polynomial time algorithm for approximating the volume of convex bodies. In: STOC, pp. 375\u2013381. ACM, New York (1989)"},{"issue":"4","key":"5_CR9","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: How good is the information theory bound in sorting? Theor. Comput. Sci.\u00a01(4), 355\u2013361 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"5_CR10","first-page":"47","volume":"10","author":"A.M. Frieze","year":"1985","unstructured":"Frieze, A.M.: Value of a random minimum spanning tree problem. J. Algorithms\u00a010(1), 47\u201356 (1985)","journal-title":"J. Algorithms"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: Sorting and selection with structured costs. In: FOCS, pp. 416\u2013425 (2001)","DOI":"10.1109\/SFCS.2001.959916"},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/11538462_7","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Gupta","year":"2005","unstructured":"Gupta, A., Kumar, A.: Where\u2019s the winner? Max-finding and sorting with metric costs. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 74\u201385. Springer, Heidelberg (2005)"},{"issue":"3","key":"5_CR13","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1006\/jcss.1995.1077","volume":"51","author":"J. Kahn","year":"1995","unstructured":"Kahn, J., Kim, J.H.: Entropy and sorting. J. Comput. Syst. Sci.\u00a051(3), 390\u2013399 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF00565647","volume":"1","author":"J. Kahn","year":"1984","unstructured":"Kahn, J., Saks, M.: Balancing poset extensions. Order\u00a01, 113\u2013126 (1984)","journal-title":"Order"},{"key":"5_CR15","unstructured":"Kannan, S., Khanna, S.: Selection with monotone comparison cost. In: SODA, pp. 10\u201317 (2003)"},{"key":"5_CR16","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1007\/BF01111312","volume":"4","author":"S.S. Kislitsyn","year":"1968","unstructured":"Kislitsyn, S.S.: A finite partially ordered set and its corresponding set of permutations. Mathematical Notes\u00a04, 798\u2013801 (1968)","journal-title":"Mathematical Notes"},{"issue":"3","key":"5_CR17","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/S0895480196304982","volume":"11","author":"J. Koml\u00f3s","year":"1998","unstructured":"Koml\u00f3s, J., Ma, Y., Szemer\u00e9di, E.: Matching nuts and bolts in O(n logn) time. SIAM J. Discrete Math.\u00a011(3), 347\u2013372 (1998)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"5_CR18","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1137\/0213049","volume":"13","author":"N. Linial","year":"1984","unstructured":"Linial, N.: The information-theoretic bound is good for merging. SIAM J. Comput.\u00a013(4), 795\u2013801 (1984)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:21:43Z","timestamp":1619522503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_5","relation":{},"subject":[]}}