{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T15:19:20Z","timestamp":1780327160320,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T00:00:00Z","timestamp":1637020800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T00:00:00Z","timestamp":1637020800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["105-2628-E-007-010-MY3"],"award-info":[{"award-number":["105-2628-E-007-010-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["109-2634-F-007-018"],"award-info":[{"award-number":["109-2634-F-007-018"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["525039"],"award-info":[{"award-number":["525039"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009226","name":"National Security Agency","doi-asserted-by":"publisher","award":["H98230-15-1-0258"],"award-info":[{"award-number":["H98230-15-1-0258"]}],"id":[{"id":"10.13039\/100009226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00453-021-00886-9","type":"journal-article","created":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T17:02:34Z","timestamp":1637082154000},"page":"124-149","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximating Dynamic Weighted Vertex Cover with Soft Capacities"],"prefix":"10.1007","volume":"84","author":[{"given":"Hao-Ting","family":"Wei","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wing-Kai","family":"Hon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Horn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chung-Shou","family":"Liao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,11,16]]},"reference":[{"issue":"3","key":"886_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1236457.1236460","volume":"54","author":"A Andersson","year":"2007","unstructured":"Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 54(3), 13 (2007)","journal-title":"J. ACM"},{"issue":"3","key":"886_CR2","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1016\/j.ejor.2019.07.062","volume":"280","author":"C Archetti","year":"2020","unstructured":"Archetti, C., Feillet, D., Mor, A., Speranza, M.G.: Dynamic traveling salesman problem with stochastic release dates. Eur. J. Oper. Res. 280(3), 832\u2013844 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"886_CR3","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/130914140","volume":"44","author":"S Baswana","year":"2015","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in $$O(\\log n)$$ update time. SIAM J. Comput. 44(1), 88\u2013113 (2015)","journal-title":"SIAM J. Comput."},{"key":"886_CR4","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Chakrabarty, D., Henzinger, M.: Fully dynamic approximate maximum matching and minimum vertex cover in $$O(\\log ^3 n)$$ worst case update time. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), Barcelona, Spain, pp. 470\u2013489 (2017)","DOI":"10.1137\/1.9781611974782.30"},{"key":"886_CR5","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Chakrabarty, D., Henzinger, M.: Deterministic fully dynamic approximate vertex cover and fractional matching in $$O(1)$$ amortized update time. In: Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO), Waterloo, Canada, pp. 86\u201398 (2017)","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"886_CR6","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. In: Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, USA, pp. 785\u2013804 (2015)","DOI":"10.1137\/1.9781611973730.54"},{"key":"886_CR7","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Design of dynamic algorithms via primal-dual method. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Heidelberg, Germany, vol. 2015, pp. 206\u2013218 (2015)","DOI":"10.1007\/978-3-662-47672-7_17"},{"issue":"2","key":"886_CR8","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1287\/ijoc.1070.0231","volume":"20","author":"LS Buriol","year":"2008","unstructured":"Buriol, L.S., Resende, M.G.C., Thorup, M.: Speeding up dynamic shortest-path algorithms. Inf. J. Comput. 20(2), 191\u2013204 (2008)","journal-title":"Inf. J. Comput."},{"issue":"2","key":"886_CR9","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1137\/S0097539703422479","volume":"36","author":"J Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Naor, J.: Covering problems with hard capacities. SIAM J. Comput. 36(2), 498\u2013515 (2006)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"886_CR10","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demetrescu","year":"2004","unstructured":"Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. J. ACM 51(6), 968\u2013992 (2004)","journal-title":"J. ACM"},{"issue":"1","key":"886_CR11","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00053-1","volume":"48","author":"S Guha","year":"2003","unstructured":"Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering. J. Algorithms 48(1), 257\u2013270 (2003)","journal-title":"J. Algorithms"},{"key":"886_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Kumar, A., Panigrahi, D.: Online and dynamic algorithms for set cover. In: Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), Montreal, Canada, pp. 537\u2013550 (2017)","DOI":"10.1145\/3055399.3055493"},{"issue":"4","key":"886_CR13","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"MTJ Holm","year":"2001","unstructured":"Holm, M.T.J., de Lichtenberg, K.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"886_CR14","doi-asserted-by":"crossref","unstructured":"Ivkovic, Z., Lloyd, E.L.: Fully dynamic maintenance of vertex cover. In: Proceedings of the 19th International Workshop on Graph-theoretic Concepts in Computer Science (WG), London, UK, pp. 99\u2013111 (1994)","DOI":"10.1007\/3-540-57899-4_44"},{"key":"886_CR15","unstructured":"Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S., Thorup, M.: Faster worst case deterministic dynamic connectivity. In: Proceedings of the 24th Annual European Symposium on Algorithms (ESA), Aarhus, Denmark, vol. 57, pp. 1\u201315 (2016)"},{"issue":"1","key":"886_CR16","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/2700206","volume":"12","author":"O Neiman","year":"2016","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algorithms 12(1), 7 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"886_CR17","doi-asserted-by":"crossref","unstructured":"Onak, K., Rubinfeld, R.: Maintaining a large matching and a small vertex cover. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), Cambridge, USA, pp. 457\u2013464 (2010)","DOI":"10.1145\/1806689.1806753"},{"key":"886_CR18","doi-asserted-by":"crossref","unstructured":"Peleg, D., Solomon, S.: Dynamic (1+$$\\epsilon $$)-approximate matchings: a density-sensitive approach. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), Virginia, USA, pp. 712\u2013729 (2016)","DOI":"10.1137\/1.9781611974331.ch51"},{"key":"886_CR19","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.ejor.2020.08.018","volume":"290","author":"A Silva","year":"2020","unstructured":"Silva, A., Aloise, D., Coelho, L.C., Rocha, C.: Heuristics for the dynamic facility location problem with modular capacities. Eur. J. Oper. Res. 290, 435\u2013452 (2020)","journal-title":"Eur. J. Oper. Res."},{"key":"886_CR20","doi-asserted-by":"crossref","unstructured":"Solomon, S.: Fully dynamic maximal matching in constant update time. In: Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), New Jersey, USA, pp. 325\u2013334 (2016)","DOI":"10.1109\/FOCS.2016.43"},{"key":"886_CR21","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), Baltimore, MD, USA, pp. 112\u2013119 (2005)","DOI":"10.1145\/1060590.1060607"},{"key":"886_CR22","first-page":"1","volume":"19","author":"G Yu","year":"2017","unstructured":"Yu, G., Yang, Y.: Dynamic routing with real-time traffic information. Oper. Res. 19, 1\u201326 (2017)","journal-title":"Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00886-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00886-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00886-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:07:12Z","timestamp":1643033232000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00886-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,16]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["886"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00886-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,16]]},"assertion":[{"value":"10 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}