{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T02:51:00Z","timestamp":1725936660137},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_36","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T16:45:34Z","timestamp":1513874734000},"page":"508-522","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Inversions from Sorting with Distance-Based Errors"],"prefix":"10.1007","author":[{"given":"Barbara","family":"Geissmann","sequence":"first","affiliation":[]},{"given":"Paolo","family":"Penna","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"issue":"2","key":"36_CR1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2701427","volume":"12","author":"M Ajtai","year":"2016","unstructured":"Ajtai, M., Feldman, V., Hassidim, A., Nelson, J.: Sorting and selection with imprecise comparisons. ACM Trans. Algorithms 12(2), 19 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"4\u20135","key":"36_CR2","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1017\/S0963548304006297","volume":"13","author":"L Alonso","year":"2004","unstructured":"Alonso, L., Chassaing, P., Gillet, F., Janson, S., Reingold, E.M., Schott, R.: Quicksort with unreliable comparisons: a probabilistic analysis. Comb. Probab. Comput. 13(4\u20135), 419\u2013449 (2004)","journal-title":"Comb. Probab. Comput."},{"key":"36_CR3","unstructured":"Braverman, M., Mossel, E.: Noisy sorting without resampling. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 268\u2013276 (2008)"},{"key":"36_CR4","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17327-1","volume-title":"Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information","author":"F Cicalese","year":"2013","unstructured":"Cicalese, F.: Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. MTCSAES. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-17327-1"},{"issue":"2","key":"36_CR5","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1111\/j.2517-6161.1977.tb01624.x","volume":"39","author":"P Diaconis","year":"1977","unstructured":"Diaconis, P., Graham, R.L.: Spearman\u2019s footrule as a measure of disarray. J. Roy. Stat. Soc.: Ser. B (Methodol.) 39(2), 262\u2013268 (1977)","journal-title":"J. Roy. Stat. Soc.: Ser. B (Methodol.)"},{"issue":"5","key":"36_CR6","doi-asserted-by":"crossref","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":"3","key":"36_CR7","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.comgeo.2004.12.007","volume":"31","author":"S Funke","year":"2005","unstructured":"Funke, S., Mehlhorn, K., N\u00e4her, S.: Structural filtering: a paradigm for efficient and exact geometric programs. Comput. Geom. 31(3), 179\u2013194 (2005)","journal-title":"Comput. Geom."},{"key":"36_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-319-22177-9_18","volume-title":"Fundamentals of Computation Theory","author":"B Geissmann","year":"2015","unstructured":"Geissmann, B., Mihal\u00e1k, M., Widmayer, P.: Recurring comparison faults: sorting and finding the minimum. In: Kosowski, A., Walukiewicz, I. (eds.) FCT 2015. LNCS, vol. 9210, pp. 227\u2013239. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-22177-9_18"},{"key":"36_CR9","unstructured":"Geissmann, B., Penna, P.: Sort well with energy-constrained comparisons. arXiv e-prints, arXiv:1610.09223 , October 2016"},{"key":"36_CR10","first-page":"85","volume":"31","author":"P Hadjicostas","year":"2005","unstructured":"Hadjicostas, P., Lakshmanan, K.B.: Bubble sort with erroneous comparisons. Australas. J. Comb. 31, 85\u2013106 (2005)","journal-title":"Australas. J. Comb."},{"key":"36_CR11","first-page":"259","volume":"98","author":"P Hadjicostas","year":"2011","unstructured":"Hadjicostas, P., Lakshmanan, K.B.: Measures of disorder and straight insertion sort with erroneous comparisons. ARS Combinatoria 98, 259\u2013288 (2011)","journal-title":"ARS Combinatoria"},{"issue":"14","key":"36_CR12","doi-asserted-by":"crossref","first-page":"1398","DOI":"10.1016\/j.dam.2011.05.010","volume":"159","author":"P Hadjicostas","year":"2011","unstructured":"Hadjicostas, P., Lakshmanan, K.B.: Recursive merge sort with erroneous comparisons. Discret. Appl. Math. 159(14), 1398\u20131417 (2011)","journal-title":"Discret. Appl. Math."},{"key":"36_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/978-3-642-23719-5_62","volume-title":"Algorithms \u2013 ESA 2011","author":"R Klein","year":"2011","unstructured":"Klein, R., Penninger, R., Sohler, C., Woodruff, D.P.: Tolerant algorithms. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 736\u2013747. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23719-5_62"},{"issue":"9","key":"36_CR14","doi-asserted-by":"crossref","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":"36_CR15","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1137\/S0097539796305298","volume":"29","author":"FT Leighton","year":"1999","unstructured":"Leighton, F.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."},{"issue":"2","key":"36_CR16","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1006\/jcss.1997.1470","volume":"54","author":"FT Leighton","year":"1997","unstructured":"Leighton, F.T., Ma, Y., Plaxton, C.G.: Breaking the theta (n log $${^2}$$ 2 n) barrier for sorting with faults. J. Comput. Syst. Sci. 54(2), 265\u2013304 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2s","key":"36_CR17","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/2465787.2465789","volume":"12","author":"KV Palem","year":"2013","unstructured":"Palem, K.V., Lingamneni, A.: Ten years of building broken chips: the physics and engineering of inexact computing. ACM Trans. Embed. Comput. Syst. 12(2s), 87 (2013)","journal-title":"ACM Trans. Embed. Comput. Syst."},{"issue":"1\u20132","key":"36_CR18","doi-asserted-by":"crossref","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. Theoret. Comput. Sci. 270(1\u20132), 71\u2013109 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"36_CR19","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1037\/h0070288","volume":"34","author":"LL Thurstone","year":"1927","unstructured":"Thurstone, L.L.: A law of comparative judgment. Psychol. Rev. 34(4), 273 (1927)","journal-title":"Psychol. Rev."},{"issue":"1","key":"36_CR20","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/0214009","volume":"14","author":"AC-C Yao","year":"1985","unstructured":"Yao, A.C.-C., Yao, F.F.: On fault-tolerant networks for sorting. SIAM J. Comput. 14(1), 120\u2013128 (1985)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,29]],"date-time":"2024-06-29T23:45:04Z","timestamp":1719704704000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}