{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T11:06:24Z","timestamp":1771067184455,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T00:00:00Z","timestamp":1534204800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["618091"],"award-info":[{"award-number":["618091"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["4002-00542"],"award-info":[{"award-number":["4002-00542"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["CA15140"],"award-info":[{"award-number":["CA15140"]}],"id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0480-z","type":"journal-article","created":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T09:08:46Z","timestamp":1534237726000},"page":"1450-1489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":52,"title":["On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6020-1646","authenticated-orcid":false,"given":"Dirk","family":"Sudholt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,14]]},"reference":[{"key":"480_CR1","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1017\/S0963548315000127","volume":"25","author":"J-B Baillon","year":"2016","unstructured":"Baillon, J.-B., Cominetti, R., Vaisman, J.: A sharp uniform bound for the distribution of sums of Bernoulli trials. Comb. Probab. Comput. 25, 352\u2013361 (2016)","journal-title":"Comb. Probab. Comput."},{"key":"480_CR2","doi-asserted-by":"crossref","unstructured":"Chen, T., Lehre, P.K., Tang, K., Yao, X.: When is an estimation of distribution algorithm better than an evolutionary algorithm? In: Proceedings of the IEEE Congress on Evolutionary Computation. IEEE Press, pp. 1470\u20131477 (2009)","DOI":"10.1109\/CEC.2009.4983116"},{"key":"480_CR3","doi-asserted-by":"crossref","unstructured":"Dang, D., Lehre, P.K.: Simplified runtime analysis of estimation of distribution algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 513\u2013518 (2015)","DOI":"10.1145\/2739480.2754814"},{"key":"480_CR4","volume-title":"Theory of Randomized Search Heuristics","author":"B Doerr","year":"2011","unstructured":"Doerr, B.: Analyzing randomized search heuristics: tools from probability theory. In: Auger, A., Doerr, B. (eds.) Theory of Randomized Search Heuristics. World Scientific, Singapore (2011)"},{"key":"480_CR5","doi-asserted-by":"crossref","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 1967\u20131974 (2010)","DOI":"10.1109\/CEC.2010.5586097"},{"key":"480_CR6","doi-asserted-by":"crossref","unstructured":"Doerr, C., Lengler, J.: OneMax in black-box models with several restrictions. In: Proceedings of the Genetic and Evolutionary Computation Conference. ACM Press, pp. 1431\u20131438 (2015)","DOI":"10.1145\/2739480.2754678"},{"issue":"3","key":"480_CR7","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s11047-006-9001-0","volume":"5","author":"S Droste","year":"2006","unstructured":"Droste, S.: A rigorous analysis of the compact genetic algorithm for linear functions. Nat. Comput. 5(3), 257\u2013283 (2006)","journal-title":"Nat. Comput."},{"key":"480_CR8","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s00224-004-1177-z","volume":"39","author":"S Droste","year":"2006","unstructured":"Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39, 525\u2013544 (2006)","journal-title":"Theory Comput. Syst."},{"key":"480_CR9","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, New York (1968)"},{"key":"480_CR10","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1971","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 2. Wiley, New York (1971)"},{"key":"480_CR11","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S.: EDAs cannot be balanced and stable. In: Proceedings of GECCO\u201916, pp. 1139\u20131146 (2016)","DOI":"10.1145\/2908812.2908895"},{"key":"480_CR12","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Sutton, A.M.: The benefit of recombination in noisy evolutionary search. In: Proceedings of the 26th International Symposium on Algorithms and Computation. Springer, pp. 140\u2013150 (2015)","DOI":"10.1007\/978-3-662-48971-0_13"},{"issue":"3","key":"480_CR13","first-page":"477","volume":"21","author":"T Friedrich","year":"2017","unstructured":"Friedrich, T., Ktzing, 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)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"1","key":"480_CR14","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1214\/aop\/1176996461","volume":"3","author":"LJ Gleser","year":"1975","unstructured":"Gleser, L.J.: On the distribution of the number of successes in independent trials. Ann. Probab. 3(1), 182\u2013188 (1975)","journal-title":"Ann. Probab."},{"issue":"4","key":"480_CR15","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/4235.797971","volume":"3","author":"GR Harik","year":"1999","unstructured":"Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE Trans. Evol. Comput. 3(4), 287\u2013297 (1999)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"480_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.swevo.2011.08.003","volume":"1","author":"M Hauschild","year":"2011","unstructured":"Hauschild, M., Pelikan, M.: An introduction and survey of estimation of distribution algorithms. Swarm Evol. Comput. 1(3), 111\u2013128 (2011)","journal-title":"Swarm Evol. Comput."},{"key":"480_CR17","unstructured":"Johannsen, D.: Random Combinatorial Structures and Randomized Search Heuristics. Ph.D. thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany and the Max-Planck-Institut f\u00fcr Informatik (2010)"},{"key":"480_CR18","doi-asserted-by":"publisher","unstructured":"Krejca, M., Witt, C.: Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax. Theor. Comput. Sci. (2018, to appear); preprint at \n                    https:\/\/doi.org\/10.1016\/j.tcs.2018.06.004","DOI":"10.1016\/j.tcs.2018.06.004"},{"key":"480_CR19","doi-asserted-by":"crossref","unstructured":"Krejca, M.S., Witt, C.: Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax. In: Proceedings of FOGA\u00a02017. ACM Press, pp. 65\u201379 (2017)","DOI":"10.1145\/3040718.3040724"},{"key":"480_CR20","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. In: Proceedings of GECCO\u201917. ACM Press, pp. 414\u2013434 (2017)","DOI":"10.1145\/3071178.3071317"},{"key":"480_CR21","unstructured":"Lehre, P.\u00a0K., Witt, C.: Concentrated hitting times of randomized search heuristics with variable drift. In: Proceedings of the 25th International Symposium on Algorithms and Computation, vol. 8889 of Lecture Notes in Computer Science. Springer, pp. 686\u2013697 (2014). Extended version at \n                    arXiv:1307.2559"},{"key":"480_CR22","unstructured":"Lehre, P.K., Witt, C.: General drift analysis with tail bounds. ArXiv e-prints (2017). \n                    arXiv:1307.2559"},{"key":"480_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68276-1","volume-title":"Inequalities: Theory of Majorization and Its Applications","author":"AW Marshall","year":"2011","unstructured":"Marshall, A.W., Olkin, I., Arnold, B.C.: Inequalities: Theory of Majorization and Its Applications, 2nd edn. Springer, Berlin (2011)","edition":"2"},{"key":"480_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"1","key":"480_CR25","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s11721-008-0023-3","volume":"3","author":"F Neumann","year":"2009","unstructured":"Neumann, F., Sudholt, D., Witt, C.: Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intell. 3(1), 35\u201368 (2009)","journal-title":"Swarm Intell."},{"key":"480_CR26","doi-asserted-by":"crossref","unstructured":"Neumann, F., Sudholt, D., Witt, C.: A few ants are enough: ACO with iteration-best update. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 63\u201370 (2010)","DOI":"10.1145\/1830483.1830493"},{"key":"480_CR27","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theor. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"480_CR28","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","volume":"545","author":"JE Rowe","year":"2014","unstructured":"Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1, \n                    \n                      \n                    \n                    $$\\lambda $$\n                    \n                      \n                        \u03bb\n                      \n                    \n                  ) evolutionary algorithm. Theor. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"480_CR29","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","volume":"16","author":"T St\u00fctzle","year":"2000","unstructured":"St\u00fctzle, T., Hoos, H.H.: MAX-MIN ant system. J.Future Gen. Comput. Syst. 16, 889\u2013914 (2000)","journal-title":"J.Future Gen. Comput. Syst."},{"issue":"3","key":"480_CR30","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"D Sudholt","year":"2013","unstructured":"Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17(3), 418\u2013435 (2013)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"480_CR31","doi-asserted-by":"crossref","unstructured":"Sudholt, D., Witt, C.: Update strength in EDAs and ACO: how to avoid genetic drift. In: Proceedings of the Genetic and Evolutionary Computation Conference, New York, NY, USA. ACM, pp. 61\u201368 (2016)","DOI":"10.1145\/2908812.2908867"},{"issue":"2","key":"480_CR32","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"C Witt","year":"2013","unstructured":"Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb. Probab. Comput. 22(2), 294\u2013318 (2013)","journal-title":"Comb. Probab. Comput."},{"key":"480_CR33","doi-asserted-by":"publisher","unstructured":"Witt, C.: Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax. Algorithmica (2018, to appear); preprint at \n                    https:\/\/doi.org\/10.1007\/s00453-018-0463-0","DOI":"10.1007\/s00453-018-0463-0"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0480-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0480-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0480-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T02:41:45Z","timestamp":1569033705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0480-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,14]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["480"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0480-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,14]]},"assertion":[{"value":"5 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}