{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:49Z","timestamp":1787340829143,"version":"build-2736575974"},"reference-count":10,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1993,4]]},"abstract":"<jats:p>Randomized algorithms for two sorting problems are presented. In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order of every pair of adjacent vertices. In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set. Lower bounds for the problems in the comparison model are described and it is shown that the algorithms are optimal within a constant factor.<\/jats:p>","DOI":"10.1137\/0222020","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:56Z","timestamp":1109227136000},"page":"272-283","source":"Crossref","is-referenced-by-count":11,"title":["Optimal Randomized Algorithms for Local Sorting and Set-Maxima"],"prefix":"10.1137","volume":"22","author":[{"given":"Wayne","family":"Goddard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claire","family":"Kenyon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonard J.","family":"Schulman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0405001"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"W. Goddard, V. King, L. J. Schulman,  Optimal randomized algorithms for local sorting and setmaxima,  Proceedings of the 22nd ACM Symposium on Theory of Computing,  1990,  45\u201353","DOI":"10.1145\/100216.100222"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322206"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"C. Kenyon, V. King,  Verifying partial orders,  Proceedings of the 21st ACM Symposium on Theory of Computing,  1989,  367\u2013374","DOI":"10.1145\/73007.73042"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579443"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579408"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0213008"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90108-8"},{"key":"R9","unstructured":"R. Tarjan, private communication"},{"key":"R10","unstructured":"A. Yao, private communication"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0222020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:50:57Z","timestamp":1787338257000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0222020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,4]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,4]]}},"alternative-id":["10.1137\/0222020"],"URL":"https:\/\/doi.org\/10.1137\/0222020","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,4]]}}}