{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:01:13Z","timestamp":1768705273608,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T00:00:00Z","timestamp":1635724800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T00:00:00Z","timestamp":1635724800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["SNF 200021_165524"],"award-info":[{"award-number":["SNF 200021_165524"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"abstract":"Abstract<\/jats:title>We consider the approximate minimum selection<\/jats:italic> problem in presence of independent random comparison faults<\/jats:italic>. This problem asks to select one of the smallest k<\/jats:italic> elements in a linearly-ordered collection of n<\/jats:italic> elements by only performing unreliable<\/jats:italic> pairwise comparisons: whenever two elements are compared, there is a small probability that the wrong comparison outcome is observed. We design a randomized algorithm that solves this problem with a success probability of at least $$1-q$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n q<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for $$q \\in (0, \\frac{n-k}{n})$$<\/jats:tex-math>\n \n q<\/mml:mi>\n \u2208<\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n \n \n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and any $$k \\in [1, n-1]$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> using $$O\\big ( \\frac{n}{k} \\big \\lceil \\log \\frac{1}{q} \\big \\rceil \\big )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n k<\/mml:mi>\n <\/mml:mfrac>\n \n \u2308<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mo>\n \n 1<\/mml:mn>\n q<\/mml:mi>\n <\/mml:mfrac>\n \n \u2309<\/mml:mo>\n <\/mml:mrow>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> comparisons in expectation (if $$k \\ge n$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or $$q \\ge \\frac{n-k}{n}$$<\/jats:tex-math>\n \n q<\/mml:mi>\n \u2265<\/mml:mo>\n \n \n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the problem becomes trivial). Then, we prove that the expected number of comparisons needed by any algorithm that succeeds with probability at least $$1-q$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n q<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> must be $${\\varOmega }(\\frac{n}{k}\\log \\frac{1}{q})$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n k<\/mml:mi>\n <\/mml:mfrac>\n log<\/mml:mo>\n \n 1<\/mml:mn>\n q<\/mml:mi>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> whenever q<\/jats:italic> is bounded away from $$\\frac{n-k}{n}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, thus implying that the expected number of comparisons performed by our algorithm is asymptotically optimal in this range. Moreover, we show that the approximate minimum selection problem can be solved using $$O( (\\frac{n}{k} + \\log \\log \\frac{1}{q}) \\log \\frac{1}{q})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n k<\/mml:mi>\n <\/mml:mfrac>\n +<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n \n 1<\/mml:mn>\n q<\/mml:mi>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mo>\n \n 1<\/mml:mn>\n q<\/mml:mi>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> comparisons in the worst case<\/jats:italic>, which is optimal when q<\/jats:italic> is bounded away from $$\\frac{n-k}{n}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$k = O\\big ( \\frac{n}{\\log \\log \\frac{1}{q}}\\big )$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \n log<\/mml:mo>\n log<\/mml:mo>\n \n 1<\/mml:mn>\n q<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfrac>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-021-00880-1","type":"journal-article","created":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T13:02:46Z","timestamp":1635771766000},"page":"60-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximate Minimum Selection with Unreliable Comparisons"],"prefix":"10.1007","volume":"84","author":[{"given":"Stefano","family":"Leucci","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9683-5982","authenticated-orcid":false,"given":"Chih-Hung","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,1]]},"reference":[{"issue":"1","key":"880_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-218X(96)00012-1","volume":"74","author":"M Aigner","year":"1997","unstructured":"Aigner, M.: Finding the maximum and minimum. Discret. Appl. Math. 74(1), 1\u201312 (1997)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"880_CR2","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/2436256.2436262","volume":"56","author":"G Anthes","year":"2013","unstructured":"Anthes, G.: Inexact design: beyond fault-tolerance. Commun. ACM 56(4), 18\u201320 (2013)","journal-title":"Commun. ACM"},{"issue":"4","key":"880_CR3","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0020-0190(92)90203-8","volume":"43","author":"A Bagchi","year":"1992","unstructured":"Bagchi, A.: On sorting in the presence of erroneous information. Inf. Process. Lett. 43(4), 213\u2013215 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"880_CR4","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1109\/TDMR.2005.853449","volume":"5","author":"RC Baumann","year":"2005","unstructured":"Baumann, R.C.: Radiation-induced soft errors in advanced semiconductor technologies. IEEE Trans. Device Mater. Reliab. 5(3), 305\u2013316 (2005)","journal-title":"IEEE Trans. Device Mater. Reliab."},{"key":"880_CR5","doi-asserted-by":"crossref","unstructured":"Borgstrom, R.S., Kosaraju, S.R.: Comparison-based search in the presence of errors. In: Proceedings of the Twenty-fifth Symposium on Theory of Computing (STOC93), pp. 130\u2013136 (1993)","DOI":"10.1145\/167088.167129"},{"key":"880_CR6","doi-asserted-by":"crossref","unstructured":"Braverman, M., Mao, J., Weinberg, S.M.: Parallel algorithms for select and partition with noisy comparisons. In: Proceedings of the Forty-Eighth 48th Symposium on Theory of Computing (STOC16), pp. 851\u2013862 (2016)","DOI":"10.1145\/2897518.2897642"},{"key":"880_CR7","unstructured":"Braverman, M., Mossel, E.: Noisy sorting without resampling. In: Proceedings of the Nineteenth Symposium on Discrete Algorithms (SODA08), pp. 268\u2013276 (2008)"},{"key":"880_CR8","unstructured":"Catania, J.A.: Soft errors in electronic memory\u2014a white paper (2004)"},{"key":"880_CR9","doi-asserted-by":"crossref","unstructured":"Cheemavalagu, S., Korkmaz, P., Palem, K.: Ultra low-energy computing via probabilistic algorithms and devices: CMOS device primitives and the energy-probability relationship. In: Proceedings of the 2004 International Conference on Solid State Devices and Materials, pp. 402\u2013403 (2004)","DOI":"10.7567\/SSDM.2004.P1-8L"},{"key":"880_CR10","unstructured":"Cheemavalagu, S., Korkmaz, P., Palem, K., Akgul, B.E.S., Chakrapani, L.N.: A probabilistic CMOS switch and its realization by exploiting noise. In: Proceedings of the 2005 IFIP\/IEEE International Conference on Very Large Scale Integration\u2014System on a Chip (VLSI-SoC05, pp. 535\u2013541 (2005)"},{"key":"880_CR11","doi-asserted-by":"crossref","unstructured":"Chen, X., Gopi, S., Mao, J., Schneider, J.: Competitive analysis of the top-$$k$$ ranking problem. In: Proceedings of the Twenty-Eighth Symposium on Discrete Algorithms (SODA17), pp. 1245\u20131264 (2017)","DOI":"10.1137\/1.9781611974782.81"},{"key":"880_CR12","doi-asserted-by":"crossref","unstructured":"Cicalese, F.: Fault-Tolerant Search Algorithms\u2014Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. Springer (2013)","DOI":"10.1007\/978-3-642-17327-1"},{"issue":"2","key":"880_CR13","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1080\/0025570X.2017.1415584","volume":"91","author":"T Edgar","year":"2018","unstructured":"Edgar, T.: Staircase series. Math. Mag. 91(2), 92\u201395 (2018)","journal-title":"Math. Mag."},{"issue":"5","key":"880_CR14","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"issue":"44","key":"880_CR15","doi-asserted-by":"publisher","first-page":"4457","DOI":"10.1016\/j.tcs.2009.07.026","volume":"410","author":"I Finocchi","year":"2009","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci. 410(44), 4457\u20134470 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.07.026","journal-title":"Theor. Comput. Sci."},{"key":"880_CR16","unstructured":"Geissmann, B., Leucci, S., Liu, C., Penna, P.: Sorting with recurrent comparison errors. In: Proceedings of the Twenty-Eighth International Symposium on Algorithms and Computation (ISAAC17), pp. 38:1\u201338:12 (2017)"},{"key":"880_CR17","unstructured":"Geissmann, B., Leucci, S., Liu, C., Penna, P.: Optimal sorting with persistent comparison errors. In: Proceedings of the Twenty-seventh European Symposium on Algorithms (ESA19), pp. 49:1\u201349:14 (2019)"},{"issue":"3","key":"880_CR18","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/s00224-019-09957-5","volume":"64","author":"B Geissmann","year":"2020","unstructured":"Geissmann, B., Leucci, S., Liu, C., Penna, P.: Optimal dislocation with persistent errors in subquadratic time. Theory Comput. Syst. 64(3), 508\u2013521 (2020). https:\/\/doi.org\/10.1007\/s00224-019-09957-5","journal-title":"Theory Comput. Syst."},{"key":"880_CR19","doi-asserted-by":"publisher","unstructured":"Geissmann, B., Leucci, S., Liu, C., Penna, P., Proietti, G.: Dual-mode greedy algorithms can save energy. In: Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC19), LIPIcs, vol. 149, pp. 64:1\u201364:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.64","DOI":"10.4230\/LIPIcs.ISAAC.2019.64"},{"key":"880_CR20","doi-asserted-by":"crossref","unstructured":"Geissmann, B., Mihal\u00e1k, M., Widmayer, P.: Recurring comparison faults: sorting and finding the minimum. In: Proceedings of the Twentieth International Symposium on Fundamentals of Computation Theory (FCT15), pp. 227\u2013239 (2015)","DOI":"10.1007\/978-3-319-22177-9_18"},{"key":"880_CR21","doi-asserted-by":"crossref","unstructured":"Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: Proceedings of the Thirty-Nineth Symposium on Theory of Computing (STOC07), pp. 95\u2013103 (2007)","DOI":"10.1145\/1250790.1250806"},{"key":"880_CR22","doi-asserted-by":"crossref","unstructured":"Klein, R., Penninger, R., Sohler, C., Woodruff, D.P.: Tolerant algorithms. In: Proceedings of the Nineteenth European Symposium on Algorithms (ESA11), pp. 736\u2014747 (2011)","DOI":"10.1007\/978-3-642-23719-5_62"},{"issue":"9","key":"880_CR23","doi-asserted-by":"publisher","first-page":"1081","DOI":"10.1109\/12.83656","volume":"40","author":"KB Lakshmanan","year":"1991","unstructured":"Lakshmanan, K.B., Ravikumar, B., Ganesan, K.: Coping with erroneous information while sorting. IEEE Trans. Comput. 40(9), 1081\u20131084 (1991)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"880_CR24","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1137\/S0097539796305298","volume":"29","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Ma, Y.: Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults. SIAM J. Comput. 29(1), 258\u2013273 (1999)","journal-title":"SIAM J. Comput."},{"key":"880_CR25","doi-asserted-by":"publisher","unstructured":"Leucci, S., Liu, C., Meierhans, S.: Resilient dictionaries for randomly unreliable memory. In: Proceedings of the 27th Annual European Symposium on Algorithms, (ESA19), LIPIcs, vol. 144, pp. 70:1\u201370:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.70","DOI":"10.4230\/LIPIcs.ESA.2019.70"},{"key":"880_CR26","unstructured":"Long, P.M.: Sorting and searching with a faulty comparison oracle. University of California at Santa Cruz, Tech. rep. (1992)"},{"key":"880_CR27","doi-asserted-by":"crossref","unstructured":"Makarychev, K., Makarychev, Y., Vijayaraghavan, A.: Sorting noisy data with partial information. In: Proceedings of the Fourth Conference on Innovations in Theoretical Computer Science (ITCS13), pp. 515\u2013528 (2013)","DOI":"10.1145\/2422436.2422492"},{"key":"880_CR28","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd edn. Cambridge University Press (2017)"},{"key":"880_CR29","doi-asserted-by":"crossref","unstructured":"Palem, K., Lingamneni, A.: Ten years of building broken chips: The physics and engineering of inexact computing. ACM Trans. Embed. Comput. Syst. 12(2s), 87:1\u201387:23 (2013)","DOI":"10.1145\/2465787.2465789"},{"issue":"2","key":"880_CR30","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0304-3975(89)90077-7","volume":"63","author":"A Pelc","year":"1989","unstructured":"Pelc, A.: Searching with known error probability. Theor. Comput. Sci. 63(2), 185\u2013202 (1989)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"880_CR31","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0304-3975(01)00303-6","volume":"270","author":"A Pelc","year":"2002","unstructured":"Pelc, A.: Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci. 270(1\u20132), 71\u2013109 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"880_CR32","doi-asserted-by":"crossref","unstructured":"Ravikumar, B., Ganesan, K., Lakshmanan, K.B.: On selecting the largest element in spite of erroneous information. In: Proceedings of the Fourth Symposium on Theoretical Aspects of Computer Science (STACs87), pp. 88\u201399 (1987)","DOI":"10.1007\/BFb0039597"},{"issue":"3","key":"880_CR33","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1016\/0022-0000(80)90014-8","volume":"20","author":"RL Rivest","year":"1980","unstructured":"Rivest, R.L., Meyer, A.R., Kleitman, D.J., Winklmann, K., Spencer, J.: Coping with errors in binary search procedures. J. Comput. Syst. Sci. 20(3), 396\u2013404 (1980)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00880-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00880-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00880-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:07:58Z","timestamp":1643033278000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00880-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["880"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00880-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,1]]},"assertion":[{"value":"5 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}