{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:26:43Z","timestamp":1759847203963,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,3,19]],"date-time":"2018-03-19T00:00:00Z","timestamp":1521417600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_165524"],"award-info":[{"award-number":["200021_165524"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004240","name":"Akademie V\u011bd \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["17-10090Y"],"award-info":[{"award-number":["17-10090Y"]}],"id":[{"id":"10.13039\/501100004240","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00453-018-0429-2","type":"journal-article","created":{"date-parts":[[2018,3,19]],"date-time":"2018-03-19T07:57:04Z","timestamp":1521446224000},"page":"796-827","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Sorting by Swaps with Noisy Comparisons"],"prefix":"10.1007","volume":"81","author":[{"given":"Tom\u00e1\u0161","family":"Gaven\u010diak","sequence":"first","affiliation":[]},{"given":"Barbara","family":"Geissmann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0004-7629","authenticated-orcid":false,"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,19]]},"reference":[{"key":"429_CR1","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2015.04.008","volume":"605","author":"Y Akimoto","year":"2015","unstructured":"Akimoto, Y., Morales, S.A., Teytaud, O.: Analysis of runtime of optimization algorithms for noisy functions over discrete codomains. Theor. Comput. Sci. 605, 42\u201350 (2015). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2015.04.008","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"429_CR2","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1137\/0404042","volume":"4","author":"S Assaf","year":"1991","unstructured":"Assaf, S., Upfal, E.: Fault tolerant sorting networks. SIAM J. Discrete Math. 4(4), 472\u2013480 (1991). \n                    https:\/\/doi.org\/10.1137\/0404042","journal-title":"SIAM J. Discrete Math."},{"key":"429_CR3","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2015.09.032","volume":"617","author":"S Astete-Morales","year":"2016","unstructured":"Astete-Morales, S., Cauwet, M., Liu, J., Teytaud, O.: Simple and cumulative regret for continuous noisy optimization. Theor. Comput. Sci. 617, 12\u201327 (2016). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2015.09.032","journal-title":"Theor. Comput. Sci."},{"key":"429_CR4","doi-asserted-by":"publisher","unstructured":"Astete-Morales, S., Cauwet, M., Teytaud, O.: Evolution strategies with additive noise: a convergence rate lower bound. In: He, J., Jansen, T., Ochoa, G., Zarges, C. (eds.) Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17\u201320, 2015, pp. 76\u201384. ACM (2015). \n                    https:\/\/doi.org\/10.1145\/2725494.2725500","DOI":"10.1145\/2725494.2725500"},{"key":"429_CR5","doi-asserted-by":"publisher","unstructured":"Astete-Morales, S., Cauwet, M., Teytaud, O.: Analysis of different types of regret in continuous noisy optimization. In: Friedrich, T., Neumann, F., Sutton A.M. (eds.) Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Denver, CO, USA, July 20\u201324, 2016, pp. 205\u2013212. ACM (2016). \n                    https:\/\/doi.org\/10.1145\/2908812.2908933","DOI":"10.1145\/2908812.2908933"},{"key":"429_CR6","doi-asserted-by":"crossref","DOI":"10.1142\/7438","volume-title":"Theory of Randomized Search Heuristics: Foundations and Recent Developments, Series on Theoretical Computer Science","author":"A Auger","year":"2011","unstructured":"Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments, Series on Theoretical Computer Science, vol. 1. World Scientific Publishing Co. Inc., River Edge (2011)"},{"key":"429_CR7","unstructured":"Benjamini, I., Berger, N., Hoffman, C., Mossel, E.: Mixing times of the biased card shuffling and the asymmetric exclusion process. Trans. Am. Math. Soc. 357(8), 3013\u20133029 (2005). \n                    http:\/\/www.jstor.org\/stable\/3845086"},{"issue":"2","key":"429_CR8","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0045-7825(99)00386-2","volume":"186","author":"HG Beyer","year":"2000","unstructured":"Beyer, H.G.: Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practice. Comput. Methods Aappl. Mech. Eng. 186(2), 239\u2013267 (2000). \n                    https:\/\/doi.org\/10.1016\/s0045-7825(99)00386-2","journal-title":"Comput. Methods Aappl. Mech. Eng."},{"issue":"1\u20132","key":"429_CR9","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s10472-015-9486-2","volume":"76","author":"M Cauwet","year":"2016","unstructured":"Cauwet, M., Liu, J., Rozi\u00e8re, B., Teytaud, O.: Algorithm portfolios for noisy optimization. Ann. Math. Artif. Intell. 76(1\u20132), 143\u2013172 (2016). \n                    https:\/\/doi.org\/10.1007\/s10472-015-9486-2","journal-title":"Ann. Math. Artif. Intell."},{"issue":"2","key":"429_CR10","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/s00453-016-0187-y","volume":"78","author":"D Dang","year":"2017","unstructured":"Dang, D., Jansen, T., Lehre, P.K.: Populations can be essential in tracking dynamic optima. Algorithmica 78(2), 660\u2013680 (2017). \n                    https:\/\/doi.org\/10.1007\/s00453-016-0187-y","journal-title":"Algorithmica"},{"key":"429_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03423-1","volume-title":"Evolutionary Algorithms in Engineering Applications","author":"D Dasgupta","year":"1997","unstructured":"Dasgupta, D., Michalewicz, Z.: Evolutionary Algorithms in Engineering Applications, 1st edn. Springer, Secaucus (1997). \n                    https:\/\/doi.org\/10.1007\/978-3-662-03423-1","edition":"1"},{"key":"429_CR12","unstructured":"Diaconis, P.: Group Representations in Probability and Statistics, vol.\u00a011. Institute of Mathematical Statistics (1998). \n                    http:\/\/www.jstor.org\/stable\/4355560"},{"key":"429_CR13","unstructured":"Diaconis, P., Graham, R.L.: Spearman\u2019s footrule as a measure of disarray. J. R. Stat. Soc. Ser. B (Methodol.) 39(2), 262\u2013268 (1977). \n                    http:\/\/www.jstor.org\/stable\/2984804"},{"key":"429_CR14","doi-asserted-by":"publisher","unstructured":"Doerr, B., Happ, E.: Directed trees: a powerful representation for sorting and ordering problems. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2008, June 1\u20136, 2008, Hong Kong, China, pp. 3606\u20133613. IEEE (2008). \n                    https:\/\/doi.org\/10.1109\/CEC.2008.4631286","DOI":"10.1109\/CEC.2008.4631286"},{"key":"429_CR15","doi-asserted-by":"publisher","unstructured":"Droste, S.: Analysis of the (1\n                    \n                      \n                    \n                    $$+$$\n                    \n                      \n                        +\n                      \n                    \n                  1) EA for a noisy OneMax. In: Deb, K., Poli, R., Banzhaf, W., Beyer, H., Burke, E.K., Darwen, P.J., Dasgupta, D., Floreano, D., Foster, J.A., Harman, M., Holland, O., Lanzi, P.L., Spector, L., Tettamanzi, A., Thierens, D., Tyrrell, A.M. (eds.) Genetic and Evolutionary Computation\u2014GECCO 2004, Genetic and Evolutionary Computation Conference, Seattle, WA, USA, June 26\u201330, 2004, Proceedings, Part I, Lecture Notes in Computer Science, vol. 3102, pp. 1088\u20131099. Springer (2004). \n                    https:\/\/doi.org\/10.1007\/978-3-540-24854-5_107","DOI":"10.1007\/978-3-540-24854-5_107"},{"issue":"3","key":"429_CR16","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1109\/TEVC.2016.2613739","volume":"21","author":"T Friedrich","year":"2017","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Sutton, A.M.: The compact genetic algorithm is efficient under extreme gaussian noise. IEEE Trans. Evol. Comput. 21(3), 477\u2013490 (2017). \n                    https:\/\/doi.org\/10.1109\/TEVC.2016.2613739","journal-title":"IEEE Trans. Evol. Comput."},{"key":"429_CR17","doi-asserted-by":"publisher","unstructured":"Gavenciak, T., Geissmann, B., Lengler, J.: Sorting by swaps with noisy comparisons. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, July 15\u201319, 2017, pp. 1375\u20131382 (2017). \n                    https:\/\/doi.org\/10.1145\/3071178.3071242","DOI":"10.1145\/3071178.3071242"},{"key":"429_CR18","unstructured":"Geissmann, B., Penna, P.: Sort well with energy-constrained comparisons. ArXiv e-prints (2016). \n                    arxiv:1610.09223"},{"issue":"1\u20132","key":"429_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.3233\/FI-2009-0005","volume":"90","author":"J Giesen","year":"2009","unstructured":"Giesen, J., Schuberth, E., Stojakovi\u0107, M.: Approximate sorting. Fundam. Inform. 90(1\u20132), 67\u201372 (2009). \n                    https:\/\/doi.org\/10.3233\/FI-2009-0005","journal-title":"Fundam. Inform."},{"issue":"3","key":"429_CR20","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/s00453-015-0072-0","volume":"75","author":"C Gie\u00dfen","year":"2016","unstructured":"Gie\u00dfen, C., K\u00f6tzing, T.: Robustness of populations in stochastic environments. Algorithmica 75(3), 462\u2013489 (2016). \n                    https:\/\/doi.org\/10.1007\/s00453-015-0072-0","journal-title":"Algorithmica"},{"key":"429_CR21","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"RL Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, 2nd edn. Addison-Wesley Professional, Reading (1994)","edition":"2"},{"key":"429_CR22","unstructured":"Hadjicostas, P., Monico, C.: A new inequality related to the Diaconis-Graham inequalities and a new characterisation of the dihedral group. Australas. J. Comb. 63(2), 226\u2013245 (2015). \n                    https:\/\/ajc.maths.uq.edu.au\/pdf\/63\/ajc_v63_p226.pdf"},{"key":"429_CR23","doi-asserted-by":"publisher","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective. Natural Computing Series. Springer Science & Business Media (2013). \n                    https:\/\/doi.org\/10.1007\/978-3-642-17339-4","DOI":"10.1007\/978-3-642-17339-4"},{"key":"429_CR24","unstructured":"Kelly, F.: Reversibility and stochastic networks. Wiley Series in Probability and Mathematical Statistics: Tracts on Probability and Statistics. Wiley (1979). \n                    http:\/\/www.statslab.cam.ac.uk\/~frank\/BOOKS\/kelly_book.html"},{"key":"429_CR25","doi-asserted-by":"publisher","unstructured":"K\u00f6tzing, T., Lissovoi, A., Witt, C.: (1\n                    \n                      \n                    \n                    $$+$$\n                    \n                      \n                        +\n                      \n                    \n                  1) EA on generalized dynamic OneMax. In: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17\u201320, 2015, pp. 40\u201351 (2015). \n                    https:\/\/doi.org\/10.1145\/2725494.2725502","DOI":"10.1145\/2725494.2725502"},{"key":"429_CR26","unstructured":"Levin, D., Peres, Y.: Markov Chains and Mixing Times, 2nd edn. MBK. American Mathematical Society (2017). \n                    http:\/\/pages.uoregon.edu\/dlevin\/MARKOV\/mcmt2e.pdf"},{"key":"429_CR27","doi-asserted-by":"publisher","unstructured":"Liu, J., St-Pierre, D.L., Teytaud, O.: A mathematically derived number of resamplings for noisy optimization. In: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO Comp \u201914, pp. 61\u201362. ACM, New York, NY, USA (2014). \n                    https:\/\/doi.org\/10.1145\/2598394.2598458","DOI":"10.1145\/2598394.2598458"},{"key":"429_CR28","unstructured":"Ma, Y.: Fault-tolerant sorting networks. Ph.D. thesis, Massachusetts Institute of Technology (1994). \n                    http:\/\/hdl.handle.net\/1721.1\/28131"},{"key":"429_CR29","doi-asserted-by":"publisher","unstructured":"Merelo, J., Chelly, Z., Mora, A., Fern\u00e1ndez-Ares, A., Esparcia-Alc\u00e1zar, A.I., Cotta, C., de\u00a0las Cuevas, P., Rico, N.: A statistical approach to dealing with noisy fitness in evolutionary algorithms. In: Computational Intelligence: International Joint Conference, IJCCI 2014 Rome, Italy, October 22\u201324, 2014 Revised Selected Papers, pp. 79\u201395. Springer (2016). \n                    https:\/\/doi.org\/10.1007\/978-3-319-26393-9_6","DOI":"10.1007\/978-3-319-26393-9_6"},{"issue":"1\u20133","key":"429_CR30","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0012-365X(03)00205-X","volume":"274","author":"LH Mitchell","year":"2004","unstructured":"Mitchell, L.H.: Maximal total absolute displacement of a permutation. Discrete Math 274(1\u20133), 319\u2013321 (2004). \n                    https:\/\/doi.org\/10.1016\/S0012-365X(03)00205-X","journal-title":"Discrete Math"},{"key":"429_CR31","doi-asserted-by":"publisher","unstructured":"Neumann, F., Witt, C.: Bioinspired Comptation in Combinatorial Optimization: Algorithms and Their Computational Complexity, 1st edn. Springer, New York (2010). \n                    https:\/\/doi.org\/10.1007\/978-3-642-16544-3","DOI":"10.1007\/978-3-642-16544-3"},{"issue":"1","key":"429_CR32","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01530781","volume":"5","author":"AE Nix","year":"1992","unstructured":"Nix, A.E., Vose, M.D.: Modeling genetic algorithms with markov chains. Ann. Math. Artif. Intell. 5(1), 77\u201388 (1992). \n                    https:\/\/doi.org\/10.1007\/BF01530781","journal-title":"Ann. Math. Artif. Intell."},{"key":"429_CR33","doi-asserted-by":"publisher","unstructured":"Qian, C., Yu, Y., Jin, Y., Zhou, Z.: On the effectiveness of sampling for evolutionary optimization in noisy environments.8672, 302\u2013311 (2014). \n                    https:\/\/doi.org\/10.1007\/978-3-319-10762-2_30","DOI":"10.1007\/978-3-319-10762-2_30"},{"key":"429_CR34","doi-asserted-by":"publisher","unstructured":"Qian, C., Yu, Y., Zhou, Z.H.: Analyzing evolutionary optimization in noisy environments. Evol. Comput. (2015). \n                    https:\/\/doi.org\/10.1162\/EVCO_a_00170","DOI":"10.1162\/EVCO_a_00170"},{"key":"429_CR35","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.swevo.2016.09.002","volume":"33","author":"P Rakshit","year":"2017","unstructured":"Rakshit, P., Konar, A., Das, S.: Noisy evolutionary optimization algorithms\u2014a comprehensive survey. Swarm Evol. Comput. 33, 18\u201345 (2017). \n                    https:\/\/doi.org\/10.1016\/j.swevo.2016.09.002","journal-title":"Swarm Evol. Comput."},{"key":"429_CR36","doi-asserted-by":"publisher","unstructured":"Safe, M.D., Carballido, J.A., Ponzoni, I., Brignole, N.B.: On stopping criteria for genetic algorithms. In: Advances in Artificial Intelligence\u2014SBIA 2004, 17th Brazilian Symposium on Artificial Intelligence, S\u00e3o Luis, Maranh\u00e3o, Brazil, September 29\u2014October 1, 2004, Proceedings, pp. 405\u2013413 (2004). \n                    https:\/\/doi.org\/10.1007\/978-3-540-28645-5_41","DOI":"10.1007\/978-3-540-28645-5_41"},{"issue":"4","key":"429_CR37","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1023\/B:JMMA.0000049379.14872.f5","volume":"3","author":"J Scharnow","year":"2004","unstructured":"Scharnow, J., Tinnefeld, K., Wegener, I.: The analysis of evolutionary algorithms on sorting and shortest paths problems. J. Math. Model. Algorithms 3(4), 349\u2013366 (2004). \n                    https:\/\/doi.org\/10.1007\/s10852-005-2584-0","journal-title":"J. Math. Model. Algorithms"},{"issue":"2","key":"429_CR38","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/0001-8708(70)90034-4","volume":"5","author":"F Spitzer","year":"1970","unstructured":"Spitzer, F.: Interaction of markov processes. Adv. Math. 5(2), 246\u2013290 (1970). \n                    https:\/\/doi.org\/10.1016\/0001-8708(70)90034-4","journal-title":"Adv. Math."},{"issue":"1","key":"429_CR39","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s00220-009-0761-0","volume":"290","author":"CA Tracy","year":"2009","unstructured":"Tracy, C.A., Widom, H.: Asymptotics in asep with step initial condition. Commun. Math. Phys. 290(1), 129\u2013154 (2009). \n                    https:\/\/doi.org\/10.1007\/s00220-009-0761-0","journal-title":"Commun. Math. Phys."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0429-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0429-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0429-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T20:35:28Z","timestamp":1552941328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0429-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,19]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["429"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0429-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,3,19]]},"assertion":[{"value":"8 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}