{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T23:14:54Z","timestamp":1769728494349,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61802441"],"award-info":[{"award-number":["61802441"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672536"],"award-info":[{"award-number":["61672536"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61836016"],"award-info":[{"award-number":["61836016"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"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,4]]},"DOI":"10.1007\/s00453-019-00662-w","type":"journal-article","created":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T11:03:09Z","timestamp":1579518189000},"page":"906-939","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1415-0515","authenticated-orcid":false,"given":"Feng","family":"Shi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,20]]},"reference":[{"key":"662_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 Co. Inc., Singapore (2011)"},{"issue":"2","key":"662_CR2","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"1","key":"662_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1023\/A:1015059928466","volume":"1","author":"HG Beyer","year":"2002","unstructured":"Beyer, H.G., Schwefel, H.P.: Evolution strategies\u2014a comprehensive introduction. Nat. Comput. 1(1), 3\u201352 (2002)","journal-title":"Nat. Comput."},{"key":"662_CR4","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C.: Optimal parameter choices through self-adjustment: applying the 1\/5-th rule in discrete settings. In: Proceedings of the 2015 Genetic and Evolutionary Computation Conference, pp. 1335\u20131342. ACM (2015)","DOI":"10.1145\/2739480.2754684"},{"issue":"4","key":"662_CR5","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":"662_CR6","volume-title":"Design and Analysis of Approximation Algorithms","author":"DZ Du","year":"2011","unstructured":"Du, D.Z., Ko, K.I., Hu, X.: Design and Analysis of Approximation Algorithms, vol. 62. Springer, Berlin (2011)"},{"issue":"4","key":"662_CR7","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","volume":"18","author":"T Friedrich","year":"2010","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. Evol. Comput. 18(4), 617\u2013633 (2010)","journal-title":"Evol. Comput."},{"key":"662_CR8","doi-asserted-by":"crossref","unstructured":"Friedrich, T., Neumann, F.: What\u2019s hot in evolutionary computation. In: AAAI, pp. 5064\u20135066 (2017)","DOI":"10.1609\/aaai.v31i1.10639"},{"issue":"1","key":"662_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/106365603321828970","volume":"11","author":"N Hansen","year":"2003","unstructured":"Hansen, N., M\u00fcller, S.D., Koumoutsakos, P.: Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol. Comput. 11(1), 1\u201318 (2003)","journal-title":"Evol. Comput."},{"key":"662_CR10","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, 21\u201335 (2004)","journal-title":"Nat. Comput."},{"issue":"3","key":"662_CR11","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6(3), 243\u2013254 (1983)","journal-title":"Discrete Appl. Math."},{"key":"662_CR12","series-title":"Natural Computing Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective. Natural Computing Series. Springer, Berlin (2013)"},{"key":"662_CR13","doi-asserted-by":"crossref","unstructured":"Jansen, T., Oliveto, P.S., Zarges, C.: Approximating vertex cover using edge-based representations. In: Proceedings of the 12th ACM\/SIGEVO Workshop on Foundations of genetic algorithms (FOGA XII), pp. 87\u201396. ACM (2013)","DOI":"10.1145\/2460239.2460248"},{"key":"662_CR14","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of computing, pp. 767\u2013775. ACM (2002)","DOI":"10.1145\/509907.510017"},{"issue":"3","key":"662_CR15","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-$$\\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"662_CR16","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T., Lissovoi, A., Witt, C.: (1+1) EA on generalized dynamic onemax. In: Proceedings of the 13th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XIII), pp. 40\u201351. ACM (2015)","DOI":"10.1145\/2725494.2725502"},{"issue":"4","key":"662_CR17","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s00453-012-9660-4","volume":"65","author":"S Kratsch","year":"2013","unstructured":"Kratsch, S., Neumann, F.: Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica 65(4), 754\u2013771 (2013)","journal-title":"Algorithmica"},{"key":"662_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3","volume-title":"Bioinspired computation in combinatorial optimization: algorithms and their computational complexity","author":"F Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired computation in combinatorial optimization: algorithms and their computational complexity, 1st edn. Springer, New York (2010)","edition":"1"},{"key":"662_CR19","unstructured":"Neumann, F., Witt, C.: On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling. In: Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI), pp. 3742\u20133748 (2015)"},{"key":"662_CR20","unstructured":"Phillips, J.M.: Chernoff-hoeffding inequality and applications (2012). arXiv preprint arXiv:1209.6396"},{"key":"662_CR21","doi-asserted-by":"crossref","unstructured":"Pourhassan, M., Friedrich, T., Neumann, F.: On the use of the dual formulation for minimum weighted vertex cover in evolutionary algorithms. In: Proceedings of the 14th ACM\/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XIV), pp. 37\u201344. ACM (2017)","DOI":"10.1145\/3040718.3040726"},{"key":"662_CR22","doi-asserted-by":"crossref","unstructured":"Pourhassan, M., Gao, W., Neumann, F.: Maintaining 2-approximations for the dynamic vertex cover problem using evolutionary algorithms. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 903\u2013910. ACM (2015)","DOI":"10.1145\/2739480.2754700"},{"key":"662_CR23","doi-asserted-by":"crossref","unstructured":"Pourhassan, M., Shi, F., Neumann, F.: Parameterized analysis of multi-objective evolutionary algorithms and the weighted vertex cover problem. In: Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN XIV), pp. 729\u2013739. Springer (2016)","DOI":"10.1007\/978-3-319-45823-6_68"},{"key":"662_CR24","doi-asserted-by":"crossref","unstructured":"Roostapour, V., Neumann, A., Neumann, F.: On the performance of baseline evolutionary algorithms on the dynamic knapsack problem. In: the 15th International Conference on Parallel Problem Solving from Nature (PPSN XV), pp. 158\u2013169. Springer (2018)","DOI":"10.1007\/978-3-319-99253-2_13"},{"key":"662_CR25","doi-asserted-by":"crossref","unstructured":"Shi, F., Neumann, F., Wang, J.: Runtime analysis of randomized search heuristics for the dynamic weighted vertex cover problem. In: Proceedings of the 2018 Genetic and Evolutionary Computation Conference, pp. 1515\u20131522. ACM (2018)","DOI":"10.1145\/3205455.3205580"},{"issue":"2","key":"662_CR26","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1007\/s00453-018-0451-4","volume":"81","author":"F Shi","year":"2019","unstructured":"Shi, F., Schirneck, M., Friedrich, T., K\u00f6tzing, T., Neumann, F.: Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints. Algorithmica 81(2), 828\u2013857 (2019)","journal-title":"Algorithmica"},{"key":"662_CR27","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2013)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00662-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00662-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00662-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T00:20:00Z","timestamp":1665534000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00662-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,20]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["662"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00662-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,20]]},"assertion":[{"value":"14 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}