{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T18:50:06Z","timestamp":1767725406012,"version":"build-2238731810"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,5,10]],"date-time":"2018-05-10T00:00:00Z","timestamp":1525910400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,5,10]],"date-time":"2018-05-10T00:00:00Z","timestamp":1525910400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["FR2988(TOSU)"],"award-info":[{"award-number":["FR2988(TOSU)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP140103400, DP160102401"],"award-info":[{"award-number":["DP140103400, DP160102401"]}],"id":[{"id":"10.13039\/501100000923","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,15]]},"DOI":"10.1007\/s00453-018-0451-4","type":"journal-article","created":{"date-parts":[[2018,5,10]],"date-time":"2018-05-10T08:14:26Z","timestamp":1525940066000},"page":"828-857","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1415-0515","authenticated-orcid":false,"given":"Feng","family":"Shi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Schirneck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"K\u00f6tzing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,10]]},"reference":[{"key":"451_CR1","doi-asserted-by":"publisher","DOI":"10.1142\/7438","volume-title":"Theory of Randomized Search Heuristics: Foundations and Recent Developments","author":"A Auger","year":"2011","unstructured":"Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments, vol. 1. World Scientific, Singapore (2011)"},{"key":"451_CR2","unstructured":"Bienaym\u00e9, I.J.: Consid\u00e9rations \u00e0 l\u2019appui de la d\u00e9couverte de Laplace sur la loi de probabilit\u00e9 dans la m\u00e9thode des moindres carr\u00e9s. Imprimerie de Mallet-Bachelier (1853)"},{"key":"451_CR3","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C.: Optimal parameter choices through self-adjustment: Applying the 1\/5-th rule in discrete settings. In: Proceedings of the 2015 Genetic and Evolutionary Computation Conference (GECCO), pp. 1335\u20131342 (2015)","DOI":"10.1145\/2739480.2754684"},{"key":"451_CR4","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2014.11.028","volume":"567","author":"B Doerr","year":"2015","unstructured":"Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theor. Comput. Sci. 567, 87\u2013104 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"451_CR5","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"451_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the ($$1+1$$) evolutionary algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"451_CR7","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","volume":"18","author":"T Friedrich","year":"2010","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. Evol. Comput. 18, 617\u2013633 (2010)","journal-title":"Evol. Comput."},{"key":"451_CR8","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Lagodzinski, J.A.G., Neumann, F., Schirneck, M.: Analysis of the ($$1+1$$)\u00a0EA on subclasses of linear functions under uniform and linear constraints. In: Proceedings of the 14th Workshop on the Foundations of Genetic Algorithms (FOGA), pp. 45\u201354 (2017)","DOI":"10.1145\/3040718.3040728"},{"key":"451_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1023\/B:NACO.0000023417.31393.c7","volume":"3","author":"J He","year":"2004","unstructured":"He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Nat. Comput. 3, 21\u201335 (2004)","journal-title":"Nat. Comput."},{"key":"451_CR10","series-title":"Natural Computing Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms . The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms. The Computer Science Perspective. Natural Computing Series. Springer, Berlin (2013)"},{"key":"451_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"key":"451_CR12","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T., Lissovoi, A., Witt, C.: ($$1+1$$)\u00a0EA on generalized dynamic OneMax. In: Proceedings of the 13th Workshop on the Foundations of Genetic Algorithms (FOGA), pp. 40\u201351 (2015)","DOI":"10.1145\/2725494.2725502"},{"key":"451_CR13","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s00453-012-9660-4","volume":"65","author":"S Kratsch","year":"2013","unstructured":"Kratsch, S., Neumann, F.: Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica 65, 754\u2013771 (2013)","journal-title":"Algorithmica"},{"key":"451_CR14","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.swevo.2011.10.001","volume":"1","author":"E Mezura-Montes","year":"2011","unstructured":"Mezura-Montes, E., Coello, C.A.C.: Constraint-handling in nature-inspired numerical optimization: past, present and future. Swarm Evol. Comput. 1, 173\u2013194 (2011)","journal-title":"Swarm Evol. Comput."},{"key":"451_CR15","unstructured":"M\u00fchlenbein, H.: How genetic algorithms really work: Mutation and hillclimbing. In: Proceedings of the 2nd Conference on Parallel Problem Solving from Nature (PPSN), vol. 92, pp. 15\u201325 (1992)"},{"key":"451_CR16","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s11047-006-9004-x","volume":"5","author":"F Neumann","year":"2006","unstructured":"Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5, 305\u2013319 (2006)","journal-title":"Nat. Comput."},{"key":"451_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3","volume-title":"Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity","author":"F Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, Berlin (2010)"},{"key":"451_CR18","doi-asserted-by":"crossref","unstructured":"Shi, F., Schirneck, M., Friedrich, T., K\u00f6tzing, T., Neumann, F.: Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints. In: Proceedings of the 2017 Genetic and Evolutionary Computation Conference (GECCO), pp. 1407\u20131414 (2017)","DOI":"10.1145\/3071178.3071270"},{"key":"451_CR19","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, 294\u2013318 (2013)","journal-title":"Comb. Probab. Comput."},{"key":"451_CR20","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1109\/TEVC.2006.888929","volume":"11","author":"Y Zhou","year":"2007","unstructured":"Zhou, Y., He, J.: A runtime analysis of evolutionary algorithms for constrained optimization problems. IEEE Trans. Evol. Comput. 11, 608\u2013619 (2007)","journal-title":"IEEE Trans. Evol. Comput."}],"updated-by":[{"DOI":"10.1007\/s00453-020-00739-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T00:00:00Z","timestamp":1595203200000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0451-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0451-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0451-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T10:25:14Z","timestamp":1600856714000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0451-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,10]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2,15]]}},"alternative-id":["451"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0451-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,10]]},"assertion":[{"value":"31 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2020","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"In the article <i>Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints<\/i>, we claimed a worst-case runtime of and for the Multi-Objective Evolutionary Algorithm and the Multi-Objective Genetic Algorithm, respectively, on linear profit functions under dynamic uniform constraint, where denotes the difference between the original constraint bound <i>B<\/i> and the new one. The technique used to prove these results contained an error. We correct this mistake and show a weaker bound of for both algorithms instead.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}