{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T05:57:31Z","timestamp":1780639051105,"version":"3.54.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,6,11]],"date-time":"2018-06-11T00:00:00Z","timestamp":1528675200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["4002-00542"],"award-info":[{"award-number":["4002-00542"]}],"id":[{"id":"10.13039\/100008394","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-0463-0","type":"journal-article","created":{"date-parts":[[2018,6,11]],"date-time":"2018-06-11T14:11:22Z","timestamp":1528726282000},"page":"632-667","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["Upper Bounds on the Running Time of the Univariate Marginal Distribution Algorithm on OneMax"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6105-7700","authenticated-orcid":false,"given":"Carsten","family":"Witt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,6,11]]},"reference":[{"key":"463_CR1","unstructured":"Baillon, J.-B., Cominetti, R., Vaisman, J.: A sharp uniform bound for the distribution of sums of Bernoulli trials. Comb. Probab. Comput. 25(3), 352\u2013361 (2016)"},{"key":"463_CR2","doi-asserted-by":"crossref","unstructured":"Chen, T., Tang, K., Chen, G., Yao, X.: On the analysis of average time complexity of estimation of distribution algorithms. In: Proceedings of CEC\u00a0\u201907, pp. 453\u2013460 (2007)","DOI":"10.1109\/CEC.2007.4424506"},{"key":"463_CR3","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 CEC\u00a0\u201909, pp. 1470\u20131477 (2009)","DOI":"10.1109\/CEC.2009.4983116"},{"key":"463_CR4","doi-asserted-by":"crossref","unstructured":"Chen, T., Tang, K., Chen, G., Yao, X.: Rigorous time complexity analysis of univariate marginal distribution algorithm with margins. In: Proceedings of CEC \u201909, pp. 2157\u20132164 (2009)","DOI":"10.1109\/CEC.2009.4983208"},{"issue":"1","key":"463_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TEVC.2009.2040019","volume":"14","author":"T Chen","year":"2010","unstructured":"Chen, T., Tang, K., Chen, G., Yao, X.: Analysis of computational time of simple estimation of distribution algorithms. IEEE Trans. Evol. Comput. 14(1), 1\u201322 (2010)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"463_CR6","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Lehre, P.K.: Simplified runtime analysis of estimation of distribution algorithms. In: Proceedings of GECCO\u00a0\u201915, pp. 513\u2013518. ACM Press, New York (2015)","DOI":"10.1145\/2739480.2754814"},{"issue":"3","key":"463_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":"463_CR8","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 ISAAC\u00a0\u201915, pp. 140\u2013150. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48971-0_13"},{"key":"463_CR9","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S.: EDAs cannot be balanced and stable. In: Proceedings of GECCO\u00a0\u201916, pp. 1139\u20131146. ACM Press, New York (2016)","DOI":"10.1145\/2908812.2908895"},{"key":"463_CR10","doi-asserted-by":"publisher","first-page":"502","DOI":"10.2307\/1426671","volume":"14","author":"B Hajek","year":"1982","unstructured":"Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14, 502\u2013525 (1982)","journal-title":"Adv. Appl. Probab."},{"issue":"3","key":"463_CR11","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":"463_CR12","unstructured":"Johannsen, D.: Random combinatorial structures and randomized search heuristics. Ph.D. Thesis, Universit\u00e4t des Saarlandes, Germany (2010). http:\/\/scidok.sulb.uni-saarland.de\/volltexte\/2011\/3529"},{"key":"463_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1111\/j.1467-9574.1980.tb00681.x","volume":"34","author":"R Kaas","year":"1980","unstructured":"Kaas, R., Buhrman, J.M.: Mean, median and mode in binomial distributions. Stat. Neerl. 34, 13\u201318 (1980)","journal-title":"Stat. Neerl."},{"key":"463_CR14","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, pp. 65\u201379. ACM Press, New York (2017)","DOI":"10.1145\/3040718.3040724"},{"key":"463_CR15","volume-title":"Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Volume\u00a02 of Genetic Algorithms and Evolutionary Computation","year":"2002","unstructured":"Larra\u00f1aga, P., Lozano, J.A. (eds.): Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Volume\u00a02 of Genetic Algorithms and Evolutionary Computation. Springer, Berlin (2002)"},{"key":"463_CR16","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\u00a0\u201917, pp. 414\u2013434. ACM Press, New York (2017)","DOI":"10.1145\/3071178.3071317"},{"key":"463_CR17","unstructured":"Lehre, P.K., Witt, C.: Concentrated hitting times of randomized search heuristics with variable drift. In: Proceedings of ISAAC\u00a0\u201914, pp. 686\u2013697. Springer, Berlin (2014). Full technical report at arXiv:1307.2559"},{"key":"463_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-662-12788-9_6","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"C McDiarmid","year":"1998","unstructured":"McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195\u2013247. Springer, Berlin (1998)"},{"issue":"2","key":"463_CR19","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1108\/17563780910959893","volume":"2","author":"B Mitavskiy","year":"2009","unstructured":"Mitavskiy, B., Rowe, J.E., Cannings, C.: Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intell. Comput. Cybern. 2(2), 243\u2013284 (2009)","journal-title":"Int. J. Intell. Comput. Cybern."},{"key":"463_CR20","doi-asserted-by":"crossref","unstructured":"M\u00fchlenbein, H., Paass, G.: From recombination of genes to the estimation of distributions I. Binary parameters. In: Proceedings of PPSN\u00a0IV, pp. 178\u2013187. Springer, Berlin (1996)","DOI":"10.1007\/3-540-61723-X_982"},{"key":"463_CR21","doi-asserted-by":"crossref","unstructured":"Neumann, F., Sudholt, D., Witt, C.: A few ants are enough: ACO with iteration-best update. In: Proceedings of GECCO\u00a0\u201910, pp. 63\u201370. ACM Press, New York (2010)","DOI":"10.1145\/1830483.1830493"},{"key":"463_CR22","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":"463_CR23","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, $$\\lambda $$ \u03bb ) evolutionary algorithm. Theor. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"463_CR24","doi-asserted-by":"publisher","first-page":"1272","DOI":"10.1214\/aoms\/1177699998","volume":"36","author":"SM Samuels","year":"1965","unstructured":"Samuels, S.M.: On the number of successes in independent trials. Ann. Math. Stat. 36(4), 1272\u20131278 (1965)","journal-title":"Ann. Math. Stat."},{"issue":"3","key":"463_CR25","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":"463_CR26","doi-asserted-by":"crossref","unstructured":"Sudholt, D., Witt, C.: Update strength in EDAs and ACO: how to avoid genetic drift. In: Proceedings of GECCO\u00a0\u201916, pp. 61\u201368. ACM Press, New York (2016)","DOI":"10.1145\/2908812.2908867"},{"issue":"2","key":"463_CR27","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":"463_CR28","doi-asserted-by":"crossref","unstructured":"Witt, C.: Upper bounds on the runtime of the univariate marginal distribution algorithm on OneMax. In: Proceedings of GECCO\u00a0\u201917, pp. 1415\u20131422 (2017)","DOI":"10.1145\/3071178.3071216"},{"issue":"4","key":"463_CR29","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1109\/TEVC.2017.2667713","volume":"21","author":"Z Wu","year":"2017","unstructured":"Wu, Z., Michael, K., M\u00f6hring, R.H.: Stochastic runtime analysis of the cross-entropy algorithm. IEEE Trans. Evolut. Comput. 21(4), 616\u2013628 (2017)","journal-title":"IEEE Trans. Evolut. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0463-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0463-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0463-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T02:18:50Z","timestamp":1751681930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0463-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,11]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["463"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0463-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,11]]},"assertion":[{"value":"13 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}