{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:57:09Z","timestamp":1743152229878,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"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_2","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T19:02:54Z","timestamp":1725649374000},"page":"19-35","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Runtime Analysis of\u00a0Evolutionary Diversity Optimization on\u00a0a\u00a0Tri-Objective Version of\u00a0the\u00a0(LeadingOnes, TrailingZeros) Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7906-096X","authenticated-orcid":false,"given":"Denis","family":"Antipov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0036-4782","authenticated-orcid":false,"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":false,"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1295-6715","authenticated-orcid":false,"given":"Andrew M.","family":"Sutton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Alexander, B., Kortman, J., Neumann, A.: Evolution of artistic image variants through feature based diversity optimisation. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 171\u2013178. ACM (2017)","DOI":"10.1145\/3071178.3071342"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Antipov, D., Neumann, A., Neumann, F.: Rigorous runtime analysis of diversity optimization with GSEMO on OneMinMax. In: Foundations of Genetic Algorithms, FOGA 2023, pp. 3\u201314. ACM (2023)","DOI":"10.1145\/3594805.3607135"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Antipov, D., Neumann, A., Neumann, F.: Runtime analysis of evolutionary diversity optimization on the multi-objective (LeadingOnes,\u00a0TrailingZeros) problem. CoRR abs\/2404.11496 (2024). https:\/\/arxiv.org\/abs\/2404.11496","DOI":"10.1145\/3638529.3654082"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Bossek, J., Neumann, F.: Evolutionary diversity optimization and the minimum spanning tree problem. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 198\u2013206. ACM (2021)","DOI":"10.1145\/3449639.3459363"},{"issue":"3","key":"2_CR5","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"D Dang","year":"2018","unstructured":"Dang, D., et al.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22(3), 484\u2013497 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Do, A.V., Guo, M., Neumann, A., Neumann, F.: Analysis of evolutionary diversity optimization for permutation problems. ACM Trans. Evol. Learn. Optim. 2(3), 11:1\u201311:27 (2022)","DOI":"10.1145\/3561974"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Do, A.V., Guo, M., Neumann, A., Neumann, F.: Diverse approximations for monotone submodular maximization problems with a matroid constraint. In: International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5558\u20135566. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/617"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B., Gao, W., Neumann, F.: Runtime analysis of evolutionary diversity maximization for OneMinMax. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 557\u2013564. ACM (2016)","DOI":"10.1145\/2908812.2908827"},{"issue":"3","key":"2_CR9","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF02219227","volume":"29","author":"P Galle","year":"1989","unstructured":"Galle, P.: Branch & sample: a simple strategy for constraint satisfaction. BIT 29(3), 395\u2013408 (1989)","journal-title":"BIT"},{"issue":"1","key":"2_CR10","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1162\/evco_a_00274","volume":"29","author":"W Gao","year":"2021","unstructured":"Gao, W., Nallaperuma, S., Neumann, F.: Feature-based diversity optimization for problem instance classification. Evol. Comput. 29(1), 107\u2013128 (2021)","journal-title":"Evol. Comput."},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Gao, W., Neumann, F.: Runtime analysis for maximizing population diversity in single-objective optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2014, pp. 777\u2013784. ACM (2014)","DOI":"10.1145\/2576768.2598251"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0377-2217(91)90293-5","volume":"54","author":"RW Haessler","year":"1991","unstructured":"Haessler, R.W., Sweeney, P.E.: Cutting stock problems and solution procedures. Eur. J. Oper. Res. 54, 141\u2013150 (1991)","journal-title":"Eur. J. Oper. Res."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Hanaka, T., Kiyomi, M., Kobayashi, Y., Kobayashi, Y., Kurita, K., Otachi, Y.: A framework to design approximation algorithms for finding diverse solutions in combinatorial problems. In: AAAI Conference on Artificial Intelligence, AAAI 2023, pp. 3968\u20133976. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i4.25511"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Hanaka, T., Kobayashi, Y., Kurita, K., Lee, S.W., Otachi, Y.: Computing diverse shortest paths efficiently: A theoretical and experimental study. In: AAAI Conference on Artificial Intelligence, AAAI 2022, pp. 3758\u20133766. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i4.20290"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Ingmar, L., de\u00a0la Banda, M.G., Stuckey, P.J., Tack, G.: Modelling diversity of solutions. In: AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 1528\u20131535. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i02.5512"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Katz, M., Sohrabi, S.: Reshaping diverse planning. In: AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 9892\u20139899. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i06.6543"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Makatura, L., Guo, M., Schulz, A., Solomon, J., Matusik, W.: Pareto gamuts: exploring optimal designs across varying contexts. ACM Trans. Graph. 40(4), 171:1\u2013171:17 (2021)","DOI":"10.1145\/3450626.3459750"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Neumann, A., Bossek, J., Neumann, F.: Diversifying greedy sampling and evolutionary diversity optimisation for constrained monotone submodular functions. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 261\u2013269. ACM (2021)","DOI":"10.1145\/3449639.3459385"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Neumann, A., Gao, W., Doerr, C., Neumann, F., Wagner, M.: Discrepancy-based evolutionary diversity optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 991\u2013998. ACM (2018)","DOI":"10.1145\/3205455.3205532"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Neumann, A., Gao, W., Wagner, M., Neumann, F.: Evolutionary diversity optimization using multi-objective indicators. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 837\u2013845. ACM (2019)","DOI":"10.1145\/3321707.3321796"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Neumann, A., et al.: Diversity optimization for the detection and concealment of spatially defined communication networks. In: Genetic and Evolutionary Computation Conference, GECCO 2023, pp. 1436\u20131444. ACM (2023)","DOI":"10.1145\/3583131.3590405"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Nikfarjam, A., Bossek, J., Neumann, A., Neumann, F.: Computing diverse sets of high quality TSP tours by EAX-based evolutionary diversity optimisation. In: Foundations of Genetic Algorithms, FOGA 2021, pp. 9:1\u20139:11. ACM (2021)","DOI":"10.1145\/3450218.3477310"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Nikfarjam, A., Bossek, J., Neumann, A., Neumann, F.: Entropy-based evolutionary diversity optimisation for the traveling salesperson problem. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 600\u2013608. ACM (2021)","DOI":"10.1145\/3449639.3459384"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Nikfarjam, A., Neumann, A., Neumann, F.: Evolutionary diversity optimisation for the traveling thief problem. In: Genetic and Evolutionary Computation Conference, GECCO 2022, pp. 749\u2013756. ACM (2022)","DOI":"10.1145\/3512290.3528862"},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"Nikfarjam, A., Rothenberger, R., Neumann, F., Friedrich, T.: Evolutionary diversity optimisation in constructing satisfying assignments. In: Genetic and Evolutionary Computation Conference, GECCO 2023, pp. 938\u2013945. ACM (2023)","DOI":"10.1145\/3583131.3590517"},{"key":"2_CR26","unstructured":"Opris, A., Lengler, J., Sudholt, D.: A tight O($$4^{\\text{k}}$$\/$${\\rm p}_{{\\rm c}}$$) runtime bound for a ($$\\mu $$+1) GA on $${\\rm Jump}_{{\\rm k}}$$ for realistic crossover probabilities. In: Genetic and Evolutionary Computation Conference, GECCO 2024. ACM (2024, to appear)"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Pierrot, T., Richard, G., Beguir, K., Cully, A.: Multi-objective quality diversity optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2022, pp. 139\u2013147. ACM (2022)","DOI":"10.1145\/3512290.3528823"},{"key":"2_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.1007\/3-540-45110-2_21","volume-title":"Genetic and Evolutionary Computation \u2014 GECCO 2003","author":"M Wineberg","year":"2003","unstructured":"Wineberg, M., Oppacher, F.: The underlying similarity of diversity measures used in evolutionary computation. In: Cant\u00fa-Paz, E., et al. (eds.) GECCO 2003. LNCS, vol. 2724, pp. 1493\u20131504. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45110-2_21"},{"issue":"2","key":"2_CR29","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. Combin. Probab. Comput. 22(2), 294\u2013318 (2013)","journal-title":"Combin. Probab. Comput."}],"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_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T19:09:57Z","timestamp":1725649797000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70071-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700705","9783031700712"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70071-2_2","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":"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"}}]}}