{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:25:38Z","timestamp":1759847138578,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031147203"},{"type":"electronic","value":"9783031147210"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-14721-0_38","type":"book-chapter","created":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T00:02:52Z","timestamp":1660521772000},"page":"542-554","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear Functions"],"prefix":"10.1007","author":[{"given":"Frank","family":"Neumann","sequence":"first","affiliation":[]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,15]]},"reference":[{"key":"38_CR1","unstructured":"Assimi, H., Harper, O., Xie, Y., Neumann, A., Neumann, F.: Evolutionary bi-objective optimization for the dynamic chance-constrained knapsack problem based on tail bound objectives. In: ECAI, vol. 325, pp. 307\u2013314. IOS Press (2020)"},{"issue":"1","key":"38_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/mnsc.6.1.73","volume":"6","author":"A Charnes","year":"1959","unstructured":"Charnes, A., Cooper, W.W.: Chance-constrained programming. Manage. Sci. 6(1), 73\u201379 (1959)","journal-title":"Manage. Sci."},{"key":"38_CR3","series-title":"Natural Computing Series","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-29414-4","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)"},{"issue":"3","key":"38_CR4","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00453-015-0019-5","volume":"75","author":"B Doerr","year":"2016","unstructured":"Doerr, B., Doerr, C.: The impact of random initialization on the runtime of randomized search heuristics. Algorithmica 75(3), 529\u2013553 (2016)","journal-title":"Algorithmica"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C., Neumann, A., Neumann, F., Sutton, A.M.: Optimization of chance-constrained submodular functions. In: AAAI, pp. 1460\u20131467. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i02.5504"},{"key":"38_CR6","series-title":"Lecture Notes in Computer Science","first-page":"32","volume-title":"Parallel Problem Solving from Nature, PPSN XI","author":"B Doerr","year":"2010","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. In: Schaefer, R., Cotta, C., Ko\u0142odziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 32\u201341. Springer, Heidelberg (2010)"},{"issue":"1","key":"38_CR7","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65(1), 224\u2013250 (2013)","journal-title":"Algorithmica"},{"issue":"1","key":"38_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/EVCO_a_00055","volume":"21","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Jansen, T., Sudholt, D., Winzen, C., Zarges, C.: Mutation rate matters even when optimizing monotonic functions. Evol. Comput. 21(1), 1\u201327 (2013)","journal-title":"Evol. Comput."},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010, pp. 1\u20138. IEEE Press (2010)","DOI":"10.1109\/CEC.2010.5586097"},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010, pp. 1449\u20131456. ACM Press (2010)","DOI":"10.1145\/1830483.1830748"},{"issue":"4","key":"38_CR11","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(4), 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation-Recent Developments in Discrete Optimization. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-29414-4"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Doerr, B., Sudholt, D., Witt, C.: When do evolutionary algorithms optimize separable functions in parallel? In: FOGA, pp. 51\u201364. ACM (2013)","DOI":"10.1145\/2460239.2460245"},{"key":"38_CR14","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. Theoret. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"38_CR15","doi-asserted-by":"publisher","first-page":"502","DOI":"10.2307\/1426671","volume":"13","author":"B Hajek","year":"1982","unstructured":"Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 13(3), 502\u2013525 (1982)","journal-title":"Adv. Appl. Probab."},{"issue":"1","key":"38_CR16","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(1), 21\u201335 (2004)","journal-title":"Nat. Comput."},{"issue":"4","key":"38_CR17","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0166-218X(81)90004-4","volume":"3","author":"H Ishii","year":"1981","unstructured":"Ishii, H., Shiode, S., Nishida, T., Namasuya, Y.: Stochastic spanning tree problem. Discret. Appl. Math. 3(4), 263\u2013273 (1981)","journal-title":"Discret. Appl. Math."},{"key":"38_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-87700-4_5","volume-title":"Parallel Problem Solving from Nature \u2013 PPSN X","author":"J J\u00e4gersk\u00fcpper","year":"2008","unstructured":"J\u00e4gersk\u00fcpper, J.: A blend of Markov-chain and drift analysis. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 41\u201351. Springer, Heidelberg (2008)"},{"issue":"3","key":"38_CR19","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00453-010-9396-y","volume":"59","author":"J J\u00e4gersk\u00fcpper","year":"2011","unstructured":"J\u00e4gersk\u00fcpper, J.: Combining Markov-chain analysis and drift analysis. Algorithmica 59(3), 409\u2013424 (2011)","journal-title":"Algorithmica"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer, Cham (2013)","DOI":"10.1007\/978-3-642-17339-4"},{"issue":"4","key":"38_CR21","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1017\/S0963548320000565","volume":"30","author":"PK Lehre","year":"2021","unstructured":"Lehre, P.K., Witt, C.: Tail bounds on hitting times of randomized search heuristics using variable drift analysis. Combinatorics Probab. Comput. 30(4), 550\u2013569 (2021)","journal-title":"Combinatorics Probab. Comput."},{"key":"38_CR22","doi-asserted-by":"crossref","unstructured":"Lengler, J., Martinsson, A., Steger, A.: When does hillclimbing fail on monotone functions: an entropy compression argument. In: ANALCO, pp. 94\u2013102. SIAM (2019)","DOI":"10.1137\/1.9781611975505.10"},{"key":"38_CR23","doi-asserted-by":"crossref","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)","DOI":"10.1017\/CBO9780511814075"},{"key":"38_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/978-3-030-58112-1_28","volume-title":"Parallel Problem Solving from Nature \u2013 PPSN XVI","author":"A Neumann","year":"2020","unstructured":"Neumann, A., Neumann, F.: Optimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms. In: B\u00e4ck, T., et al. (eds.) PPSN 2020. LNCS, vol. 12269, pp. 404\u2013417. Springer, Cham (2020)"},{"issue":"10","key":"38_CR25","doi-asserted-by":"publisher","first-page":"3209","DOI":"10.1007\/s00453-020-00779-3","volume":"83","author":"F Neumann","year":"2021","unstructured":"Neumann, F., Pourhassan, M., Witt, C.: Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint. Algorithmica 83(10), 3209\u20133237 (2021)","journal-title":"Algorithmica"},{"key":"38_CR26","doi-asserted-by":"crossref","unstructured":"Neumann, F., Sutton, A.M.: Runtime analysis of the (1+1) evolutionary algorithm for the chance-constrained knapsack problem. In: FOGA, pp. 147\u2013153. ACM (2019)","DOI":"10.1145\/3299904.3340315"},{"key":"38_CR27","doi-asserted-by":"crossref","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer, Cham (2010)","DOI":"10.1007\/978-3-642-16544-3"},{"issue":"2","key":"38_CR28","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. Combinatorics Probab. Comput. 22(2), 294\u2013318 (2013)","journal-title":"Combinatorics Probab. Comput."},{"key":"38_CR29","doi-asserted-by":"crossref","unstructured":"Xie, Y., Harper, O., Assimi, H., Neumann, A., Neumann, F.: Evolutionary algorithms for the chance-constrained knapsack problem. In: GECCO, pp. 338\u2013346. ACM (2019)","DOI":"10.1145\/3321707.3321869"},{"key":"38_CR30","doi-asserted-by":"crossref","unstructured":"Xie, Y., Neumann, A., Neumann, F.: Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem. In: GECCO, pp. 271\u2013279. ACM (2020)","DOI":"10.1145\/3377930.3390162"},{"key":"38_CR31","doi-asserted-by":"crossref","unstructured":"Xie, Y., Neumann, A., Neumann, F.: Heuristic strategies for solving complex interacting stockpile blending problem with chance constraints. In: GECCO, pp. 1079\u20131087. ACM (2021)","DOI":"10.1145\/3449639.3459382"},{"key":"38_CR32","doi-asserted-by":"crossref","unstructured":"Xie, Y., Neumann, A., Neumann, F., Sutton, A.M.: Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. In: GECCO, pp. 1187\u20131194. ACM (2021)","DOI":"10.1145\/3449639.3459381"}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-14721-0_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T16:02:45Z","timestamp":1710259365000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-14721-0_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031147203","9783031147210"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-14721-0_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"15 August 2022","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":"Dortmund","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2022.cs.tu-dortmund.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"185","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.75","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}