{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:28Z","timestamp":1770994048148,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,11,17]],"date-time":"2015-11-17T00:00:00Z","timestamp":1447718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>\n            We consider a simple model of imprecise comparisons: there exists some \u03b4 &gt; 0 such that when a subject is given two elements to compare, if the values of those elements (as perceived by the subject) differ by at least \u03b4, then the comparison will be made correctly; when the two elements have values that are within \u03b4, the outcome of the comparison is unpredictable. This model is inspired by both imprecision in human judgment of values and also by bounded but potentially adversarial errors in the outcomes of sporting tournaments. Our model is closely related to a number of models commonly considered in the psychophysics literature where \u03b4 corresponds to the\n            <jats:italic>Just Noticeable Difference (JND) unit<\/jats:italic>\n            or\n            <jats:italic>difference threshold<\/jats:italic>\n            . In experimental psychology, the method of paired comparisons was proposed as a means for ranking preferences among\n            <jats:italic>n<\/jats:italic>\n            elements of a human subject. The method requires performing all (\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            <jats:sub>2<\/jats:sub>\n            ) comparisons, then sorting elements according to the number of wins. The large number of comparisons is performed to counter the potentially faulty decision-making of the human subject, who acts as an imprecise comparator. We show that in our model the method of paired comparisons has optimal accuracy, minimizing the errors introduced by the imprecise comparisons. However, it is also wasteful because it requires all (\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            <jats:sub>2<\/jats:sub>\n            ). We show that the same optimal guarantees can be achieved using 4\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            comparisons, and we prove the optimality of our method. We then explore the general tradeoff between the guarantees on the error that can be made and number of comparisons for the problems of sorting, max-finding, and selection. Our results provide strong lower bounds and close-to-optimal solutions for each of these problems.\n          <\/jats:p>","DOI":"10.1145\/2701427","type":"journal-article","created":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T13:42:28Z","timestamp":1447854148000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Sorting and Selection with Imprecise Comparisons"],"prefix":"10.1145","volume":"12","author":[{"given":"Mikl\u00f3s","family":"Ajtai","sequence":"first","affiliation":[{"name":"IBM Research - Almaden, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3904-759X","authenticated-orcid":false,"given":"Vitaly","family":"Feldman","sequence":"additional","affiliation":[{"name":"IBM Research - Almaden, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avinatan","family":"Hassidim","sequence":"additional","affiliation":[{"name":"Bar Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jelani","family":"Nelson","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1388240.1388242"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401028"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404042"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.58"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90095-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167129"},{"key":"e_1_2_1_8_1","volume-title":"Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information","author":"Cicalese Ferdinando","unstructured":"Ferdinando Cicalese . 2013. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information . Springer . 1--198 pages. Ferdinando Cicalese. 2013. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Springer. 1--198 pages."},{"key":"e_1_2_1_9_1","volume-title":"The Method of Paired Comparisons","author":"David Herbert Aron","unstructured":"Herbert Aron David . 1988. The Method of Paired Comparisons ( 2 nd ed.). Charles Griffin & Company Limited . Herbert Aron David. 1988. The Method of Paired Comparisons (2nd ed.). Charles Griffin & Company Limited.","edition":"2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of COLT. 277--292","author":"Feldman Vitaly","year":"2009","unstructured":"Vitaly Feldman . 2009 . Robustness of evolvability . In Proceedings of COLT. 277--292 . Vitaly Feldman. 2009. Robustness of evolvability. In Proceedings of COLT. 277--292."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.026"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007375"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00040-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210034"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603047"},{"key":"e_1_2_1_17_1","volume-title":"Karp and Robert Kleinberg","author":"Richard","year":"2007","unstructured":"Richard M. Karp and Robert Kleinberg . 2007 . Noisy binary search and its applications. In SODA. 881--890. Richard M. Karp and Robert Kleinberg. 2007. Noisy binary search and its applications. In SODA. 881--890."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476378"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970203"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1980.11976831"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00303-6"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 88--99","author":"Ravikumar Bala","unstructured":"Bala Ravikumar , K. Ganesan , and K. B. Lakshmanan . 1987. On selecting the largest element in spite of erroneous information . In Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 88--99 . Bala Ravikumar, K. Ganesan, and K. B. Lakshmanan. 1987. On selecting the largest element in spite of erroneous information. In Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 88--99."},{"key":"e_1_2_1_24_1","first-page":"505","article-title":"On a problem in information theory. Magyar Tud. Akad. Mat","volume":"6","author":"R\u00e9nyi Alfr\u00e9d","year":"1962","unstructured":"Alfr\u00e9d R\u00e9nyi . 1962 . On a problem in information theory. Magyar Tud. Akad. Mat . Kutat\u00f3 Int. K\u00f6zl 6 (1962), 505 -- 516 . Alfr\u00e9d R\u00e9nyi. 1962. On a problem in information theory. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl 6 (1962), 505--516.","journal-title":"Kutat\u00f3 Int. K\u00f6zl"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90014-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702410053"},{"key":"e_1_2_1_27_1","volume-title":"Albaum","author":"Smith Scott M.","year":"2005","unstructured":"Scott M. Smith and Gerald S . Albaum . 2005 . Fundamentals of Marketing Research (1st ed.). Sage Publications, Inc . Scott M. Smith and Gerald S. Albaum. 2005. Fundamentals of Marketing Research (1st ed.). Sage Publications, Inc."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1037\/h0070288"},{"key":"e_1_2_1_29_1","volume-title":"Adventures of a Mathematician","author":"Ulam Stanis\u0142aw Marcin","unstructured":"Stanis\u0142aw Marcin Ulam . 1976. Adventures of a Mathematician . Scribner\u2019s, New York . Stanis\u0142aw Marcin Ulam. 1976. Adventures of a Mathematician. Scribner\u2019s, New York."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204030"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214009"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2701427","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2701427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:10Z","timestamp":1750227190000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2701427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,17]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2701427"],"URL":"https:\/\/doi.org\/10.1145\/2701427","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,17]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}