{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:36:54Z","timestamp":1759847814954,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031700705"},{"type":"electronic","value":"9783031700712"}],"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-70071-2_17","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774000},"page":"264-279","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Runtime Analysis for\u00a0State-of-the-Art Multi-objective Evolutionary Algorithms on\u00a0the\u00a0Subset Selection Problem"],"prefix":"10.1007","author":[{"given":"Renzhong","family":"Deng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weijie","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingfeng","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"key":"17_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":"17_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":"17_CR3","doi-asserted-by":"publisher","unstructured":"Bian, C., Qian, C.: Better running time of\u00a0the\u00a0non-dominated sorting genetic algorithm II (NSGA-II) by\u00a0using stochastic tournament selection. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tu\u0161ar, T. (eds.) PPSN XVII, pp. 428\u2013441. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-14721-0_30","DOI":"10.1007\/978-3-031-14721-0_30"},{"key":"17_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. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/612"},{"key":"17_CR5","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. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/613"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Opris, A., Salehi, B., Sudholt, D.: A proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. In: Conference on Artificial Intelligence, AAAI 2023, pp. 12390\u201312398. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i10.26460"},{"key":"17_CR7","unstructured":"Das, A., Kempe, D.: Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In: International Conference on Machine Learning, ICML 2011, pp. 1057\u20131064. ACM (2011)"},{"key":"17_CR8","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":"17_CR9","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-29414-4"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"1288","DOI":"10.1109\/TEVC.2023.3250552","volume":"27","author":"B Doerr","year":"2023","unstructured":"Doerr, B., Qu, Z.: A first runtime analysis of the NSGA-II on a multimodal problem. IEEE Trans. Evol. Comput. 27, 1288\u20131297 (2023)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Doerr, B., Qu, Z.: Runtime analysis for the NSGA-II: provable speed-ups from crossover. In: Conference on Artificial Intelligence, AAAI 2023, pp. 12399\u201312407. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i10.26461"},{"key":"17_CR12","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":"17_CR13","doi-asserted-by":"crossref","unstructured":"Durillo, J.J., Nebro, A.J., Luna, F., Alba, E.: On the effect of the steady-state selection scheme in multi-objective genetic algorithms. In: Evolutionary Multi-criterion Optimization: 5th International Conference, EMO 2009, Nantes, 7\u201310 April 2009. Proceedings 5, pp. 183\u2013197. Springer (2009)","DOI":"10.1007\/978-3-642-01020-0_18"},{"key":"17_CR14","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":"17_CR15","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":"17_CR16","doi-asserted-by":"crossref","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms \u2013 The Computer Science Perspective. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-17339-4"},{"key":"17_CR17","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":"17_CR18","doi-asserted-by":"crossref","unstructured":"Miller, A.: Subset Selection in Regression. CRC Press (2002)","DOI":"10.1201\/9781420035933"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization \u2013 Algorithms and Their Computational Complexity. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-16544-3"},{"key":"17_CR20","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":"17_CR21","doi-asserted-by":"crossref","unstructured":"Qian, C., Li, G., Feng, C., Tang, K.: Distributed pareto optimization for subset selection. In: Lang, J. (ed.) International Joint Conference on Artificial Intelligence, IJCAI 2018, pp. 1492\u20131498. ijcai.org (2018)","DOI":"10.24963\/ijcai.2018\/207"},{"key":"17_CR22","unstructured":"Qian, C., Shi, J., Yu, Y., Tang, K., Zhou, Z.: Parallel pareto optimization for subset selection. In: International Joint Conference on Artificial Intelligence, IJCAI 2016, pp. 1939\u20131945. IJCAI\/AAAI Press (2016)"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Qian, C., Shi, J., Yu, Y., Tang, K., Zhou, Z.: Optimizing ratio of monotone set functions. In: International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 2606\u20132612. ijcai.org (2017)","DOI":"10.24963\/ijcai.2017\/363"},{"key":"17_CR24","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.artint.2013.09.002","volume":"204","author":"C Qian","year":"2013","unstructured":"Qian, C., Yu, Y., Zhou, Z.: An analysis on recombination in multi-objective evolutionary optimization. Artif. Intell. 204, 99\u2013119 (2013)","journal-title":"Artif. Intell."},{"key":"17_CR25","unstructured":"Qian, C., Yu, Y., Zhou, Z.H.: Subset selection by pareto optimization. In: Advances in Neural Information Processing Systems, NIPS 2015, vol.\u00a028. Curran Associates, Inc. (2015)"},{"key":"17_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. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/628"},{"key":"17_CR27","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.artint.2012.01.001","volume":"180","author":"Y Yu","year":"2012","unstructured":"Yu, Y., Yao, X., Zhou, Z.H.: On the approximation ability of evolutionary optimization with application to minimum set cover. Artif. Intell. 180, 20\u201333 (2012)","journal-title":"Artif. Intell."},{"key":"17_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":"17_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. Evolution. Comput. (2023). In press. https:\/\/doi.org\/10.1109\/TEVC.2023.3320278","DOI":"10.1109\/TEVC.2023.3320278"},{"key":"17_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":"17_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":"17_CR32","doi-asserted-by":"crossref","unstructured":"Zheng, W., Li, M., Deng, R., Doerr, B.: How to use the metropolis algorithm for multi-objective optimization? In: Conference on Artificial Intelligence, AAAI 2024, pp. 20883\u201320891. AAAI Press (2024)","DOI":"10.1609\/aaai.v38i18.30078"},{"key":"17_CR33","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":"17_CR34","doi-asserted-by":"publisher","unstructured":"Zhou, Z.H., Yu, Y., Qian, C.: Evolutionary Learning: Advances in Theories and Algorithms. Springer, Singapore (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-70071-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:11:28Z","timestamp":1725664288000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70071-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700705","9783031700712"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70071-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"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 that are relevant to the content of this article.","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"}}]}}