{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T05:55:32Z","timestamp":1780638932308,"version":"3.54.1"},"reference-count":60,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T00:00:00Z","timestamp":1770940800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004836","name":"Independent Research Fund Denmark","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1016\/j.artint.2026.104501","type":"journal-article","created":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T07:27:14Z","timestamp":1771054034000},"page":"104501","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":1,"special_numbering":"C","title":["Mathematical runtime analysis of a multi-Valued estimation of distribution algorithm"],"prefix":"10.1016","volume":"353","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1814-7612","authenticated-orcid":false,"given":"Sumit","family":"Adak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6105-7700","authenticated-orcid":false,"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.artint.2026.104501_bib0001","doi-asserted-by":"crossref","DOI":"10.1016\/j.tcs.2023.114074","article-title":"Bivariate estimation-of-distribution algorithms can find an exponential number of optima","volume":"971","author":"Doerr","year":"2023","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.artint.2026.104501_bib0002","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.swevo.2011.08.003","article-title":"An introduction and survey of estimation of distribution algorithms","volume":"1","author":"Hauschild","year":"2011","journal-title":"Swarm Evol. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0003","article-title":"Estimation of distribution algorithms: A new tool for evolutionary computation","volume":"2","year":"2002"},{"key":"10.1016\/j.artint.2026.104501_bib0004","series-title":"Scalable optimization via probabilistic modeling: From algorithms to applications","volume":"33","author":"Pelikan","year":"2006"},{"key":"10.1016\/j.artint.2026.104501_bib0005","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1007\/978-3-662-43505-2_45","article-title":"Estimation of distribution algorithms","author":"Pelikan","year":"2015","journal-title":"Springer Handbook Comput. Intell."},{"key":"10.1016\/j.artint.2026.104501_bib0006","series-title":"Proceedings of the Third C* Conference on Computer Science and Software Engineering","first-page":"17","article-title":"Toward an estimation of distribution algorithm for the evolution of artificial neural networks","author":"Holker","year":"2010"},{"key":"10.1016\/j.artint.2026.104501_bib0007","series-title":"IEEE Congress on Evolutionary Computation (CEC 2017)","first-page":"1579","article-title":"Estimation of distribution algorithms for the multi-Mode resource constrained project scheduling problem","author":"Ayodele","year":"2017"},{"issue":"4","key":"10.1016\/j.artint.2026.104501_bib0008","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s10696-015-9210-x","article-title":"An estimation of distribution algorithm and new computational results for the stochastic resource-constrained project scheduling problem","volume":"27","author":"Fang","year":"2015","journal-title":"Flex. Serv. Manuf. J."},{"issue":"4","key":"10.1016\/j.artint.2026.104501_bib0009","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1109\/TEVC.2013.2281524","article-title":"Multiobjective estimation of distribution algorithm based on joint modeling of objectives and variables","volume":"18","author":"Karshenas","year":"2014","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0010","series-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2024)","first-page":"1560","article-title":"A runtime analysis of bias-invariant neuroevolution and dynamic fitness evaluation","author":"Fischer","year":"2024"},{"key":"10.1016\/j.artint.2026.104501_bib0011","series-title":"Proceedings of the 17Th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2023)","first-page":"61","article-title":"First steps towards a runtime analysis of neuroevolution","author":"Fischer","year":"2023"},{"issue":"14","key":"10.1016\/j.artint.2026.104501_bib0012","first-page":"12293","article-title":"Theoretical analyses of multi-Objective evolutionary algorithms on multi-Modal objectives","volume":"35","author":"Doerr","year":"2021","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"10.1016\/j.artint.2026.104501_bib0013","doi-asserted-by":"crossref","DOI":"10.1016\/j.artint.2023.104016","article-title":"Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)","volume":"325","author":"Zheng","year":"2023","journal-title":"Artif. Intell."},{"issue":"9","key":"10.1016\/j.artint.2026.104501_bib0014","first-page":"10408","article-title":"A first mathematical runtime analysis of the non-dominated sorting genetic algorithm II (NSGA-II)","volume":"36","author":"Zheng","year":"2022","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"10.1016\/j.artint.2026.104501_bib0015","series-title":"Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22","first-page":"4800","article-title":"Runtime analysis of single- and multi-Objective evolutionary algorithms for chance constrained optimization problems with normally distributed random variables","author":"Neumann","year":"2022"},{"issue":"10","key":"10.1016\/j.artint.2026.104501_bib0016","first-page":"12399","article-title":"Runtime analysis for the NSGA-II: provable speed-Ups from crossover","volume":"37","author":"Doerr","year":"2023","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"issue":"18","key":"10.1016\/j.artint.2026.104501_bib0017","first-page":"20777","article-title":"Towards running time analysis of interactive multi-Objective evolutionary algorithms","volume":"38","author":"Lu","year":"2024","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"10.1016\/j.artint.2026.104501_bib0018","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s11047-006-9001-0","article-title":"A rigorous analysis of the compact genetic algorithm for linear functions","volume":"5","author":"Droste","year":"2006","journal-title":"Nat. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0019","doi-asserted-by":"crossref","DOI":"10.1016\/j.tcs.2024.114622","article-title":"Estimation-of-distribution algorithms for multi-valued decision variables","volume":"1003","author":"Ben Jedidia","year":"2024","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.artint.2026.104501_bib0020","series-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN 2024), Part III","first-page":"53","article-title":"Runtime analysis of a multi-valued compact genetic algorithm on generalized onemax","author":"Adak","year":"2024"},{"issue":"2","key":"10.1016\/j.artint.2026.104501_bib0021","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1162\/evco_a_00361","article-title":"Tail bounds on the runtime of categorical compact genetic algorithm","volume":"33","author":"Hamano","year":"2025","journal-title":"Evol. Comput."},{"issue":"4","key":"10.1016\/j.artint.2026.104501_bib0022","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1162\/evco.1999.7.4.353","article-title":"FDA - A Scalable evolutionary algorithm for the optimization of additively decomposed functions","volume":"7","author":"M\u00fchlenbein","year":"1999","journal-title":"Evol. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0023","series-title":"Scalable Optimization via Probabilistic Modeling","first-page":"39","article-title":"Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ecga)","author":"Harik","year":"2006"},{"key":"10.1016\/j.artint.2026.104501_bib0024","article-title":"MIMIC: Finding optima by estimating probability densities","volume":"9","author":"De Bonet","year":"1996","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.artint.2026.104501_bib0025","series-title":"Advances in Soft Computing","first-page":"521","article-title":"The bivariate marginal distribution algorithm","author":"Pelikan","year":"1999"},{"key":"10.1016\/j.artint.2026.104501_bib0026","series-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999)","first-page":"525","article-title":"BOA: The bayesian optimization algorithm","author":"Pelikan","year":"1999"},{"key":"10.1016\/j.artint.2026.104501_bib0027","series-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN 1996)","first-page":"178","article-title":"From recombination of genes to the estimation of distributions i. binary parameters","author":"M\u00fchlenbein","year":"1996"},{"key":"10.1016\/j.artint.2026.104501_bib0028","series-title":"Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning","author":"Baluja","year":"1994"},{"issue":"4","key":"10.1016\/j.artint.2026.104501_bib0029","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1109\/4235.797971","article-title":"The compact genetic algorithm","volume":"3","author":"Harik","year":"1999","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0030","series-title":"Proceedings of the European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2025)","first-page":"1","article-title":"A runtime analysis of the multi-valued compact genetic algorithm on generalized leadingones","author":"Adak","year":"2025"},{"key":"10.1016\/j.artint.2026.104501_bib0031","series-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2025)","first-page":"1585","article-title":"Improved runtime analysis of a multi-Valued compact genetic algorithm on two generalized onemax problems","author":"Adak","year":"2025"},{"key":"10.1016\/j.artint.2026.104501_bib0032","series-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","first-page":"405","article-title":"Theory of estimation-of-Distribution algorithms","author":"Krejca","year":"2020"},{"issue":"1","key":"10.1016\/j.artint.2026.104501_bib0033","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","article-title":"On the analysis of the (1+1) evolutionary algorithm","volume":"276","author":"Droste","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.artint.2026.104501_bib0034","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.tcs.2018.06.004","article-title":"Lower bounds on the run time of the univariate marginal distribution algorithm on onemax","volume":"832","author":"Krejca","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.artint.2026.104501_bib0035","doi-asserted-by":"crossref","first-page":"1096","DOI":"10.1007\/s00453-020-00778-4","article-title":"The complex parameter landscape of the compact genetic algorithm","volume":"83","author":"Lengler","year":"2021","journal-title":"Algorithmica"},{"key":"10.1016\/j.artint.2026.104501_bib0036","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1007\/s00453-018-0463-0","article-title":"Upper bounds on the running time of the univariate marginal distribution algorithm on onemax","volume":"81","author":"Witt","year":"2019","journal-title":"Algorithmica"},{"issue":"6","key":"10.1016\/j.artint.2026.104501_bib0037","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1109\/TEVC.2019.2956633","article-title":"Significance-Based estimation-of-Distribution algorithms","volume":"24","author":"Doerr","year":"2020","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0038","series-title":"Proceedings of the 18Th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms","first-page":"14","article-title":"Runtime analysis of a compact genetic algorithm with high selection pressure","author":"Adak","year":"2025"},{"key":"10.1016\/j.artint.2026.104501_bib0039","article-title":"Runtime analysis of the compact genetic algorithm on the leadingOnes benchmark","author":"Chwia\u0142kowski","year":"2025","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"1","key":"10.1016\/j.artint.2026.104501_bib0040","article-title":"On multiset selection with size constraints","volume":"32","author":"Qian","year":"2018","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"issue":"4","key":"10.1016\/j.artint.2026.104501_bib0041","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1109\/TEVC.2017.2749263","article-title":"Constrained monotone k -Submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee","volume":"22","author":"Qian","year":"2018","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"25","key":"10.1016\/j.artint.2026.104501_bib0042","first-page":"26955","article-title":"Runtime analysis for multi-Objective evolutionary algorithms in unbounded integer spaces","volume":"39","author":"Doerr","year":"2025","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"10.1016\/j.artint.2026.104501_bib0043","doi-asserted-by":"crossref","first-page":"3059","DOI":"10.1007\/s00453-020-00780-w","article-title":"The runtime of the compact genetic algorithm on jump functions","volume":"83","author":"Doerr","year":"2021","journal-title":"Algorithmica"},{"key":"10.1016\/j.artint.2026.104501_bib0044","doi-asserted-by":"crossref","first-page":"1450","DOI":"10.1007\/s00453-018-0480-z","article-title":"On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization","volume":"81","author":"Sudholt","year":"2019","journal-title":"Algorithmica"},{"key":"10.1016\/j.artint.2026.104501_bib0045","series-title":"Proceedings of the 15Th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2019)","first-page":"25","article-title":"An exponential lower bound for the runtime of the compact genetic algorithm on jump functions","author":"Doerr","year":"2019"},{"key":"10.1016\/j.artint.2026.104501_bib0046","first-page":"1","article-title":"The query complexity of finding a hidden permutation","author":"Afshani","year":"2013","journal-title":"Space-Efficient Data Struct. Stream. Algor.: Paper. Honor J. Ian Munro Occasion 66th Birthday"},{"issue":"6","key":"10.1016\/j.artint.2026.104501_bib0047","doi-asserted-by":"crossref","first-page":"1140","DOI":"10.1109\/TEVC.2020.2987361","article-title":"Sharp bounds for genetic drift in estimation of distribution algorithms","volume":"24","author":"Doerr","year":"2020","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0048","series-title":"Proceedings of the Workshop on Foundations of Genetic Algorithms (FOGA 2002)","first-page":"115","article-title":"The sensitivity of PBIL to its learning rate, and how detailed balance can remove it","author":"Shapiro","year":"2002"},{"issue":"1","key":"10.1016\/j.artint.2026.104501_bib0049","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1162\/1063656053583414","article-title":"Drift and scaling in estimation of distribution algorithms","volume":"13","author":"Shapiro","year":"2005","journal-title":"Evol. Comput."},{"key":"10.1016\/j.artint.2026.104501_bib0050","series-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN 2006)","first-page":"92","article-title":"Diversity loss in general estimation of distribution algorithms","author":"Shapiro","year":"2006"},{"key":"10.1016\/j.artint.2026.104501_bib0051","series-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018)","first-page":"1539","article-title":"Domino convergence: why one should hill-climb on linear functions","author":"Witt","year":"2018"},{"key":"10.1016\/j.artint.2026.104501_bib0052","series-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020)","first-page":"17","article-title":"The univariate marginal distribution algorithm copes well with deception and epistasis","author":"Doerr","year":"2020"},{"key":"10.1016\/j.artint.2026.104501_bib0053","series-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005)","first-page":"679","article-title":"Not all linear functions are equally difficult for the compact genetic algorithm","author":"Droste","year":"2005"},{"key":"10.1016\/j.artint.2026.104501_bib0054","series-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","first-page":"195","article-title":"Concentration","author":"McDiarmid","year":"1998"},{"key":"10.1016\/j.artint.2026.104501_bib0055","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2018.09.024","article-title":"Analyzing randomized search heuristics via stochastic domination","volume":"773","author":"Doerr","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.artint.2026.104501_bib0056","series-title":"Proceedings of the ACM Conference on Foundations of Genetic Algorithms (FOGA 2015)","first-page":"40","article-title":"(1+1) EA On generalized dynamic onemax","author":"K\u00f6tzing","year":"2015"},{"key":"10.1016\/j.artint.2026.104501_bib0057","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.tcs.2020.11.028","article-title":"A simplified run time analysis of the univariate marginal distribution algorithm on leadingones","volume":"851","author":"Doerr","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.artint.2026.104501_bib0058","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","article-title":"Concentration of first hitting times under additive drift","volume":"75","author":"K\u00f6tzing","year":"2016","journal-title":"Algorithmica"},{"key":"10.1016\/j.artint.2026.104501_bib0059","series-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","first-page":"89","article-title":"Drift analysis","author":"Lengler","year":"2020"},{"key":"10.1016\/j.artint.2026.104501_bib0060","series-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010)","first-page":"63","article-title":"A few ants are enough: ACO with iteration-best update","author":"Neumann","year":"2010"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370226000275?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370226000275?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:25:41Z","timestamp":1777425941000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370226000275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4]]},"references-count":60,"alternative-id":["S0004370226000275"],"URL":"https:\/\/doi.org\/10.1016\/j.artint.2026.104501","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[2026,4]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Mathematical runtime analysis of a multi-Valued estimation of distribution algorithm","name":"articletitle","label":"Article Title"},{"value":"Artificial Intelligence","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.artint.2026.104501","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"104501"}}