{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T11:24:54Z","timestamp":1746703494953,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP160102401"],"award-info":[{"award-number":["DP160102401"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s00453-020-00779-3","type":"journal-article","created":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T06:02:26Z","timestamp":1604469746000},"page":"3209-3237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint"],"prefix":"10.1007","volume":"83","author":[{"given":"Frank","family":"Neumann","sequence":"first","affiliation":[]},{"given":"Mojgan","family":"Pourhassan","sequence":"additional","affiliation":[]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,4]]},"reference":[{"key":"779_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. World Scientific Publishing, Singapore (2011)"},{"key":"779_CR2","doi-asserted-by":"crossref","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. In: Proceedings of PPSN\u00a0\u201910, LNCS, vol. 6238, pp. 32\u201341. Springer (2010)","DOI":"10.1007\/978-3-642-15844-5_4"},{"issue":"1","key":"779_CR3","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"},{"key":"779_CR4","doi-asserted-by":"crossref","unstructured":"Doerr, B., Pohl, S.: Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet. In: Proceedings of GECCO\u00a0\u201912, pp. 1317\u20131324. ACM Press (2012)","DOI":"10.1145\/2330163.2330346"},{"key":"779_CR5","doi-asserted-by":"crossref","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC\u00a0\u201910, pp. 1\u20138. IEEE Press (2010)","DOI":"10.1109\/CEC.2010.5586097"},{"key":"779_CR6","doi-asserted-by":"crossref","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO\u00a0\u201910, pp. 1449\u20131456. ACM Press (2010)","DOI":"10.1145\/1830483.1830748"},{"issue":"4","key":"779_CR7","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":"779_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B., Sudholt, D., Witt, C.: When do evolutionary algorithms optimize separable functions in parallel? In: Proceedings of FOGA\u00a0\u201913, pp. 51\u201364. ACM Press (2013)","DOI":"10.1145\/2460239.2460245"},{"key":"779_CR9","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."},{"issue":"6","key":"779_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2018.04.051","volume":"832","author":"T Friedrich","year":"2020","unstructured":"Friedrich, T., K\u00f6tzing, T., Lagodzinski, J.G., Neumann, F., Schirneck, M.: Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints. Theor. Comput. Sci. 832(6), 3\u201319 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"779_CR11","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":"779_CR12","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."},{"key":"779_CR13","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J.: A blend of Markov-chain and drift analysis. In: Proceedings of PPSN\u00a0\u201908, LNCS, vol. 5199, pp. 41\u201351. Springer (2008)","DOI":"10.1007\/978-3-540-87700-4_5"},{"issue":"3","key":"779_CR14","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":"779_CR15","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":"779_CR16","unstructured":"Johannsen, D.: Random combinatorial structures and randomized search heuristics. PhD thesis, Saarland University (2010)"},{"key":"779_CR17","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Witt, C.: Concentrated hitting times of randomized search heuristics with variable drift. In: Proceedings of ISAAC\u00a0\u201914, LNCS, vol. 8889, pp. 686\u2013697. Springer. Extended technical report at http:\/\/arxiv.org\/abs\/1307.2559 (2014)","DOI":"10.1007\/978-3-319-13075-0_54"},{"issue":"2","key":"779_CR18","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1108\/17563780910959893","volume":"2","author":"B Mitavskiy","year":"2009","unstructured":"Mitavskiy, B., Rowe, J.E., Cannings, C.: Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intell. Comput. Cybern. 2(2), 243\u2013284 (2009)","journal-title":"Int. J. Intell. Comput. Cybern."},{"issue":"1","key":"779_CR19","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32\u201340 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"779_CR20","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00453-009-9370-8","volume":"59","author":"F Neumann","year":"2011","unstructured":"Neumann, F., Reichel, J., Skutella, M.: Computing minimum cuts by randomized search heuristics. Algorithmica 59(3), 323\u2013342 (2011)","journal-title":"Algorithmica"},{"key":"779_CR21","first-page":"1506","volume":"2019","author":"F Neumann","year":"2019","unstructured":"Neumann, F., Pourhassan, M., Witt, C.: Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint. Proc. Genet. Evolut. Comput. Conf. GECCO 2019, 1506\u20131514 (2019)","journal-title":"Proc. Genet. Evolut. Comput. Conf. GECCO"},{"key":"779_CR22","doi-asserted-by":"crossref","unstructured":"Reichel, J., Skutella, M.: On the size of weights in randomized search heuristics. In: Proceedings of FOGA\u00a0\u201909, pp. 21\u201328. ACM Press (2009)","DOI":"10.1145\/1527125.1527130"},{"issue":"1","key":"779_CR23","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00453-008-9253-4","volume":"57","author":"J Reichel","year":"2010","unstructured":"Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. Algorithmica 57(1), 187\u2013206 (2010)","journal-title":"Algorithmica"},{"key":"779_CR24","doi-asserted-by":"crossref","unstructured":"Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1,$$\\lambda $$)\u00a0EA. In: Proceedings of GECCO\u00a0\u201912, pp. 1349\u20131356. ACM (2012)","DOI":"10.1145\/2330163.2330350"},{"key":"779_CR25","volume-title":"Evolutionary Optimization","author":"I Wegener","year":"2001","unstructured":"Wegener, I.: Methods for the analysis of evolutionary algorithmson pseudo-Boolean functions. In: Sarker, R., Mohammadian, M., Yao, X. (eds.) Evolutionary Optimization. Kluwer Academic Publishers, Dordrecht (2001)"},{"issue":"2","key":"779_CR26","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."},{"key":"779_CR27","doi-asserted-by":"crossref","unstructured":"Witt, C.: Revised analysis of the (1+1) EA for the minimum spanning tree problem. In: Proceedings of GECCO\u00a0\u201914, pp. 509\u2013516. ACM Press (2014)","DOI":"10.1145\/2576768.2598237"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00779-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00779-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00779-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T15:36:19Z","timestamp":1633102579000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00779-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,4]]},"references-count":27,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["779"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00779-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,11,4]]},"assertion":[{"value":"17 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}