{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T16:08:02Z","timestamp":1775146082538,"version":"3.50.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031700842","type":"print"},{"value":"9783031700859","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-70085-9_10","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774000},"page":"153-168","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Near-Tight Runtime Guarantees for\u00a0Many-Objective Evolutionary Algorithms"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0734-0708","authenticated-orcid":false,"given":"Simon","family":"Wietheger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9786-220X","authenticated-orcid":false,"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics. World Scientific Publishing (2011)","DOI":"10.1142\/7438"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1016\/j.ejor.2006.08.008","volume":"181","author":"N Beume","year":"2007","unstructured":"Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: Multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181, 1653\u20131669 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Bian, C., Qian, C., Tang, K.: A general approach to running time analysis of multi-objective evolutionary algorithms. In: International Joint Conference on Artificial Intelligence, IJCAI 2018, pp. 1405\u20131411. IJCAI (2018)","DOI":"10.24963\/ijcai.2018\/195"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bian, C., Zhou, Y., Li, M., Qian, C.: Stochastic population update can provably be helpful in multi-objective evolutionary algorithms. In: International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5513\u20135521 (2023). ijcai.org","DOI":"10.24963\/ijcai.2023\/612"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/978-3-540-87700-4_65","volume-title":"Parallel Problem Solving from Nature \u2013 PPSN X","author":"D Brockhoff","year":"2008","unstructured":"Brockhoff, D., Friedrich, T., Neumann, F.: Analyzing hypervolume indicator based algorithms. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 651\u2013660. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87700-4_65"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Cerf, S., Doerr, B., Hebras, B., Kahane, J., Wietheger, S.: The first proven performance guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a combinatorial optimization problem. In: International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5522\u20135530 (2023). ijcai.org","DOI":"10.24963\/ijcai.2023\/613"},{"key":"10_CR7","doi-asserted-by":"publisher","unstructured":"Coello, C.A.C., Lamont, G.B., van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, 2nd edn. (2007). https:\/\/doi.org\/10.1007\/978-0-387-36797-2","DOI":"10.1007\/978-0-387-36797-2"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1109\/TEVC.2013.2281535","volume":"18","author":"K Deb","year":"2014","unstructured":"Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans. Evol. Comput. 18, 577\u2013601 (2014)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","volume":"6","author":"K Deb","year":"2002","unstructured":"Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182\u2013197 (2002)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10_CR10","unstructured":"Do, A.V., Neumann, A., Neumann, F., Sutton, A.M.: Rigorous runtime analysis of MOEA\/D for solving multi-objective minimum weight base problems. In: Advances in Neural Information Processing Systems, NeurIPS 2023 (2023)"},{"key":"10_CR11","series-title":"Natural Computing Series","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-29414-4_1","volume-title":"Theory of Evolutionary Computation","author":"B Doerr","year":"2020","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Theory of Evolutionary Computation. NCS, pp. 1\u201387. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4_1"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, B., Kodric, B., Voigt, M.: Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In: Congress on Evolutionary Computation, CEC 2013, pp. 432\u2013439. IEEE (2013)","DOI":"10.1109\/CEC.2013.6557601"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization. Springer (2020). http:\/\/www.lix.polytechnique.fr\/Labo\/Benjamin.Doerr\/doerr_neumann_book.html","DOI":"10.1007\/978-3-030-29414-4"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B., Zheng, W.: Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In: Conference on Artificial Intelligence, AAAI 2021, pp. 12293\u201312301. AAAI Press (2021)","DOI":"10.1609\/aaai.v35i14.17459"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Fortin, F., Parizeau, M.: Revisiting the NSGA-II crowding-distance computation. In: Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 623\u2013630. ACM (2013)","DOI":"10.1145\/2463372.2463456"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: Congress on Evolutionary Computation, CEC 2003, pp. 1918\u20131925. IEEE (2003)","DOI":"10.1109\/CEC.2003.1299908"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1162\/EVCO_a_00013","volume":"18","author":"O Giel","year":"2010","unstructured":"Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimisation. Evol. Comput. 18, 335\u2013356 (2010)","journal-title":"Evol. Comput."},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Huang, Z., Zhou, Y., Luo, C., Lin, Q.: A runtime analysis of typical decomposition approaches in MOEA\/D framework for many-objective optimization problems. In: International Joint Conference on Artificial Intelligence, IJCAI 2021, pp. 1682\u20131688 (2021)","DOI":"10.24963\/ijcai.2021\/232"},{"key":"10_CR19","doi-asserted-by":"publisher","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms \u2013 The Computer Science Perspective. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-17339-4","DOI":"10.1007\/978-3-642-17339-4"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1109\/TEVC.2004.823470","volume":"8","author":"M Laumanns","year":"2004","unstructured":"Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions. IEEE Trans. Evol. Comput. 8, 170\u2013182 (2004)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-45712-7_5","volume-title":"Parallel Problem Solving from Nature \u2014 PPSN VII","author":"M Laumanns","year":"2002","unstructured":"Laumanns, M., Thiele, L., Zitzler, E., Welzl, E., Deb, K.: Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In: Guerv\u00f3s, J.J.M., Adamidis, P., Beyer, H.-G., Schwefel, H.-P., Fern\u00e1ndez-Villaca\u00f1as, J.-L. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 44\u201353. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45712-7_5"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/TEVC.2015.2501315","volume":"20","author":"YL Li","year":"2016","unstructured":"Li, Y.L., Zhou, Y.R., Zhan, Z.H., Zhang, J.: A primary theoretical study on decomposition-based multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 20, 563\u2013576 (2016)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1016\/j.ejor.2006.08.005","volume":"181","author":"F Neumann","year":"2007","unstructured":"Neumann, F.: Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. Eur. J. Oper. Res. 181, 1620\u20131629 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"10_CR24","doi-asserted-by":"publisher","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization \u2013 Algorithms and Their Computational Complexity. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-16544-3","DOI":"10.1007\/978-3-642-16544-3"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Opris, A., Dang, D.C., Neumann, F., Sudholt, D.: Runtime analyses of NSGA-III on many-objective problems. In: Genetic and Evolutionary Computation Conference, GECCO 2024. ACM (2024). to appear","DOI":"10.1145\/3638529.3654218"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Wietheger, S., Doerr, B.: A mathematical runtime analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In: International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5657\u20135665 (2023). ijcai.org","DOI":"10.24963\/ijcai.2023\/628"},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1109\/TEVC.2007.892759","volume":"11","author":"Q Zhang","year":"2007","unstructured":"Zhang, Q., Li, H.: MOEA\/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11, 712\u2013731 (2007)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"10_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104016","volume":"325","author":"W Zheng","year":"2023","unstructured":"Zheng, W., Doerr, B.: Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II). Artif. Intell. 325, 104016 (2023)","journal-title":"Artif. Intell."},{"key":"10_CR29","doi-asserted-by":"publisher","unstructured":"Zheng, W., Doerr, B.: Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives. IEEE Trans. Evol. Comput. (2023). in press, https:\/\/doi.org\/10.1109\/TEVC.2023.3320278","DOI":"10.1109\/TEVC.2023.3320278"},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1162\/evco_a_00328","volume":"31","author":"W Zheng","year":"2023","unstructured":"Zheng, W., Doerr, B.: Theoretical analyses of multiobjective evolutionary algorithms on multimodal objectives. Evol. Comput. 31, 337\u2013373 (2023)","journal-title":"Evol. Comput."},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Zheng, W., Doerr, B.: Runtime analysis of the SMS-EMOA for many-objective optimization. In: Conference on Artificial Intelligence, AAAI 2024, pp. 20874\u201320882. AAAI Press (2024)","DOI":"10.1609\/aaai.v38i18.30077"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"Zheng, W., Liu, Y., Doerr, B.: A first mathematical runtime analysis of the Non-Dominated Sorting Genetic Algorithm\u00a0II (NSGA-II). In: Conference on Artificial Intelligence, AAAI 2022, pp. 10408\u201310416. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i9.21283"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.swevo.2011.03.001","volume":"1","author":"A Zhou","year":"2011","unstructured":"Zhou, A., Qu, B.Y., Li, H., Zhao, S.Z., Suganthan, P.N., Zhang, Q.: Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evol. Comput. 1, 32\u201349 (2011)","journal-title":"Swarm Evol. Comput."},{"key":"10_CR34","doi-asserted-by":"publisher","unstructured":"Zhou, Z.H., Yu, Y., Qian, C.: Evolutionary Learning: Advances in Theories and Algorithms. Springer (2019). https:\/\/doi.org\/10.1007\/978-981-13-5956-9","DOI":"10.1007\/978-981-13-5956-9"}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVIII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-70085-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:22Z","timestamp":1725664462000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70085-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700842","9783031700859"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70085-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"7 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"PPSN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Problem Solving from Nature","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hagenberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2024.fh-ooe.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}