{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:43Z","timestamp":1787340403345,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["340506"],"award-info":[{"award-number":["340506"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["715672"],"award-info":[{"award-number":["715672"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007162","name":"Guangdong Science and Technology Department","doi-asserted-by":"publisher","award":["2020B1212030003"],"award-info":[{"award-number":["2020B1212030003"]}],"id":[{"id":"10.13039\/501100007162","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012543","name":"Shanghai Science and Technology Development Foundation","doi-asserted-by":"publisher","award":["0143\/2020\/A3"],"award-info":[{"award-number":["0143\/2020\/A3"]}],"id":[{"id":"10.13039\/100012543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012543","name":"Shanghai Science and Technology Development Foundation","doi-asserted-by":"publisher","award":["SKL-IOTSC-2021-2023"],"award-info":[{"award-number":["SKL-IOTSC-2021-2023"]}],"id":[{"id":"10.13039\/100012543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001862","name":"Svenska Forskningsr\u00e5det Formas","doi-asserted-by":"publisher","award":["2015-04659"],"award-info":[{"award-number":["2015-04659"]}],"id":[{"id":"10.13039\/501100001862","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S03353X\/1"],"award-info":[{"award-number":["EP\/S03353X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004733","name":"Universidade de Macau","doi-asserted-by":"publisher","award":["SRG2020-00020-IOTSC"],"award-info":[{"award-number":["SRG2020-00020-IOTSC"]}],"id":[{"id":"10.13039\/501100004733","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","award":["ICT 15-003"],"award-info":[{"award-number":["ICT 15-003"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal [Formula: see text] approximation factor. (Throughout, [Formula: see text], [Formula: see text], [Formula: see text], and [Formula: see text] are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when [Formula: see text], this was achieved by a deterministic [Formula: see text]-approximation algorithm with [Formula: see text] amortized update time by Gupta et al.\u00a0[ Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537\u2013550]. In this paper we consider the low-frequency range, when [Formula: see text], and obtain deterministic algorithms with a [Formula: see text]-approximation ratio and the following guarantees on the update time. (1) [Formula: see text] amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was [Formula: see text] of Bhattacharya, Henzinger, and Italiano [ Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206\u2013218]. In contrast, the only result with [Formula: see text]-approximation was that of Abboud et al.\u00a0[ Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114\u2013125], who designed a randomized [Formula: see text]-approximation algorithm with [Formula: see text] amortized update time. (2) [Formula: see text] amortized update time: This result improves the above update time bound for most values of [Formula: see text] in the low-frequency range, i.e., [Formula: see text]. It is also the first result that is independent of [Formula: see text] and [Formula: see text]. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [ Deterministically maintaining a [Formula: see text]-approximate minimum vertex cover in [Formula: see text] amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872\u20131885] for unweighted dynamic vertex cover (i.e., when [Formula: see text] and [Formula: see text]). (3) [Formula: see text] worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the [Formula: see text] worst-case update time for the unweighted dynamic vertex cover problem (i.e., when [Formula: see text] and [Formula: see text]) of Bhattacharya, Henzinger, and Nanongkai [ Fully dynamic approximate maximum matching and minimum vertex cover in [Formula: see text] worst case update time, in Proceedings SODA 2017, SIAM, pp. 470\u2013489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds.<\/jats:p>","DOI":"10.1137\/21m1428649","type":"journal-article","created":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T07:35:30Z","timestamp":1696577730000},"page":"1132-1192","source":"Crossref","is-referenced-by-count":1,"title":["Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover"],"prefix":"10.1137","volume":"52","author":[{"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry CV4 7AL, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5008-6530","authenticated-orcid":true,"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[{"name":"Institute of Science and Technology Austria (ISTA), Vienna 1090, Austria."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4468-2675","authenticated-orcid":true,"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, 66123 Saarbr\u00fccken, Germany; Saarland University, 66123 Saarbr\u00fccken, Germany; and KTH, 114 28 Stockholm, Sweden."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5766-2115","authenticated-orcid":true,"given":"Xiaowei","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Macau, Taipa, Macau, China."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,10,6]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"A. Abboud , \nR. Addanki , \nF. Grandoni , \nD. Panigrahi , and \nB. Saha , Dynamic set cover: Improved algorithms and lower bounds, in STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 114\u2013125.","DOI":"10.1145\/3313276.3316376"},{"key":"ref2","unstructured":"M. Arar , \nS. Chechik , \nS. Cohen , \nC. Stein , and \nD. Wajc , Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms, in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), LIPIcs 107, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018, pp. 79:1\u201379:16."},{"key":"ref3","unstructured":"S. Assadi  and \nS. Solomon , Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach, in Proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021), LIPIcs 204, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021, pp. 8:1\u20138:18."},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"S. Baswana , \nM. Gupta , and \nS. Sen , Fully dynamic maximal matching in O(log n) update time, in Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, 2011, pp. 383\u2013392.","DOI":"10.1109\/FOCS.2011.89"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"A. Bernstein  and \nS. Chechik , Deterministic decremental single source shortest paths: Beyond the o(mn) bound, in STOC \u201916: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 389\u2013397.","DOI":"10.1145\/2897518.2897521"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"A. Bernstein  and \nS. Chechik , Deterministic partially dynamic single source shortest paths for sparse graphs, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2017, pp. 453\u2013469, https:\/\/doi.org\/10.1137\/1.9781611974782.29.","DOI":"10.1137\/1.9781611974782.29"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"A. Bernstein , \nS. Forster , and \nM. Henzinger , A deamortization approach for dynamic spanner and dynamic maximal matching, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) SIAM, 2019, pp. 1899\u20131918, https:\/\/doi.org\/10.1137\/1.9781611975482.115.","DOI":"10.1137\/1.9781611975482.115"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya , \nD. Chakrabarty , and \nM. Henzinger , Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time, in Proceedings of IPCO 2017: Integer Programming and Combinatorial Optimization 10328 of Lecture Notes in Comput. Sci. 10328, Springer, 2017, pp. 86\u201398.","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya , \nM. Henzinger , and \nG. F. Italiano , Design of dynamic algorithms via primal-dual method, in Proceedings of ICALP 2015: Automata, Languages, and Programming, Lecture Notes in Comput. Sci. 9134, Springer, 2015, pp. 206\u2013218.","DOI":"10.1007\/978-3-662-47672-7_17"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya , \nM. Henzinger , and \nG. F. Italiano , Deterministic fully dynamic data structures for vertex cover and matching, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2015, pp. 785\u2013804, https:\/\/doi.org\/10.1137\/1.9781611973730.54.","DOI":"10.1137\/1.9781611973730.54"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.005"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya , \nM. Henzinger , and \nD. Nanongkai , New deterministic approximation algorithms for fully dynamic matching, in STOC \u201916: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 398\u2013411.","DOI":"10.1145\/2897518.2897568"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya , \nM. Henzinger , and \nD. Nanongkai , Fully dynamic approximate maximum matching and minimum vertex cover in   \\({O}(\\log^3 n)\\)   worst case update time, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2017, pp. 470\u2013489, https:\/\/doi.org\/10.1137\/1.9781611974782.30.","DOI":"10.1137\/1.9781611974782.30"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya , \nM. Henzinger , and \nD. Nanongkai , A new deterministic algorithm for dynamic set cover, in Proceedings of the 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019, pp. 406\u2013423.","DOI":"10.1109\/FOCS.2019.00033"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya , \nM. Henzinger , \nD. Nanongkai , and \nX. Wu , Dynamic set cover: Improved amortized and worst-case update time, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, pp. 2537\u20132549, https:\/\/doi.org\/10.1137\/1.9781611976465.150.","DOI":"10.1137\/1.9781611976465.150"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya  and \nJ. Kulkarni , Deterministically maintaining a   \\((2 +\\epsilon )\\)  -approximate minimum vertex cover in   \\({O}(1\/\\epsilon^2)\\)   amortized update time, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2019, pp. 1872\u20131885, https:\/\/doi.org\/10.1137\/1.9781611975482.113.","DOI":"10.1137\/1.9781611975482.113"},{"key":"ref17","unstructured":"M. Charikar  and \nS. Solomon , Fully dynamic almost-maximal matching: Breaking the polynomial worst-case time barrier, in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), LIPIcs 107, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018, pp. 33:1\u201333:14."},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy  and \nS. Khanna , A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems, in STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 389\u2013400.","DOI":"10.1145\/3313276.3316320"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"I. Dinur  and \nD. Steurer , Analytical approach to parallel repetition, in STOC \u201914: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 624\u2013633.","DOI":"10.1145\/2591796.2591884"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"A. Gupta , \nR. Krishnaswamy , \nA. Kumar , and \nD. Panigrahi , Online and dynamic algorithms for set cover, in STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 537\u2013550.","DOI":"10.1145\/3055399.3055493"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"M. Gupta  and \nR. Peng , Fully dynamic   \\((1+\\epsilon )\\)  -approximate matchings, in Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 548\u2013557.","DOI":"10.1109\/FOCS.2013.65"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"M. Henzinger , \nS. Krinninger , and \nD. Nanongkai , Decremental single-source shortest paths on undirected graphs in near-linear total update time, in Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), 2014, pp. 146\u2013155.","DOI":"10.1109\/FOCS.2014.24"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"M. Henzinger , \nS. Krinninger , and \nD. Nanongkai , Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs, in STOC \u201914: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, 2014, pp. 674\u2013683.","DOI":"10.1145\/2591796.2591869"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/140957299"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/3218657"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"K. G. Larsen , The cell probe complexity of dynamic range counting, in STOC \u201912: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012, pp. 85\u201394.","DOI":"10.1145\/2213977.2213987"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"K. G. Larsen , \nO. Weinstein , and \nH. Yu , Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds, in STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 978\u2013989.","DOI":"10.1145\/3188745.3188790"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"D. Nanongkai  and \nT. Saranurak , Dynamic spanning forest with worst-case update time: Adaptive, Las Vegas, and   \\({O}(n^{1\/2-\\epsilon })\\)  -time, in STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 1122\u20131129.","DOI":"10.1145\/3055399.3055447"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"D. Nanongkai , \nT. Saranurak , and \nC. Wulff-Nilsen , Dynamic minimum spanning forest with subpolynomial worst-case update time, in Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 950\u2013961.","DOI":"10.1109\/FOCS.2017.92"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"D. Nanongkai , \nT. Saranurak , and \nS. Yingchareonthawornchai , Breaking quadratic time for small vertex connectivity and an approximation scheme, in STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pp. 241\u2013252.","DOI":"10.1145\/3313276.3316394"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"O. Neiman  and \nS. Solomon , Simple deterministic algorithms for fully dynamic maximal matching, in STOC \u201913: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, pp. 745\u2013754.","DOI":"10.1145\/2488608.2488703"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"K. Onak  and \nR. Rubinfeld , Maintaining a large matching and a small vertex cover, in STOC \u201910: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, 2010, pp. 457\u2013464.","DOI":"10.1145\/1806689.1806753"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"D. Peleg  and \nS. Solomon , Dynamic   \\((1+\\epsilon)\\)  -approximate matchings: A density-sensitive approach, in SODA \u201916: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2016, pp. 712\u2013729, https:\/\/doi.org\/10.1137\/1.9781611974331.ch51.","DOI":"10.1137\/1.9781611974331.ch51"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0887"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"S. Solomon , Fully dynamic maximal matching in constant update time, in Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016, pp. 325\u2013334.","DOI":"10.1109\/FOCS.2016.43"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1428649","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:34Z","timestamp":1787337214000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1428649"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,6]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1137\/21M1428649"],"URL":"https:\/\/doi.org\/10.1137\/21m1428649","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,6]]}}}