{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:44:39Z","timestamp":1787507079785,"version":"build-2736575974"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n                    We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our article are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in \u211d\n                    <jats:sup>1<\/jats:sup>\n                    and \u211d\n                    <jats:sup>2<\/jats:sup>\n                    . The first framework uses bootstrapping and gives a (1 + \u03b5)-approximate data structure for dynamic interval set cover in \u211d\n                    <jats:sup>1<\/jats:sup>\n                    with\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>\u03b1<\/jats:sup>\n                    \/ \u03b5) amortized update time for any constant \u03b1 &gt; 0; in \u211d\n                    <jats:sup>2<\/jats:sup>\n                    , this method gives\n                    <jats:italic>O<\/jats:italic>\n                    (1)-approximate data structures for unit-square set cover and hitting set with\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>1\/2+\u03b1<\/jats:sup>\n                    ) amortized update time. The second framework uses local modification and leads to a (1 + \u03b5)-approximate data structure for dynamic interval hitting set in \u211d\n                    <jats:sup>1<\/jats:sup>\n                    with \u00d5(1\/\u03b5) amortized update time; in \u211d\n                    <jats:sup>2<\/jats:sup>\n                    , it gives\n                    <jats:italic>O<\/jats:italic>\n                    (1)-approximate data structures for unit-square set cover and hitting set in the\n                    <jats:italic>partially<\/jats:italic>\n                    dynamic settings with \u00d5(1) amortized update time.\n                  <\/jats:p>","DOI":"10.1145\/3551639","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T08:15:10Z","timestamp":1660119310000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Geometric Set Cover and Hitting Set"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj","family":"Agarwal","sequence":"first","affiliation":[{"name":"Duke University, Durham, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6714-7988","authenticated-orcid":false,"given":"Hsien-Chih","family":"Chang","sequence":"additional","affiliation":[{"name":"Dartmouth College, Hanover, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5668-7521","authenticated-orcid":false,"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3300-7842","authenticated-orcid":false,"given":"Allen","family":"Xiao","sequence":"additional","affiliation":[{"name":"Duke University, Durham, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7015-1988","authenticated-orcid":false,"given":"Jie","family":"Xue","sequence":"additional","affiliation":[{"name":"New York Universtiy Shanghai, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/3313276.3316376","volume-title":"51st Annual ACM SIGACT Symposium on Theory of Computing","author":"Abboud Amir","year":"2019","unstructured":"Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. 2019. Dynamic set cover: Improved algorithms and lower bounds. In 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM, 114\u2013125."},{"key":"e_1_3_2_3_2","volume-title":"36th International Symposium on Computational Geometry (SoCG)","author":"Agarwal Pankaj K.","year":"2020","unstructured":"Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. 2020. Dynamic geometric set cover and hitting set. In 36th International Symposium on Computational Geometry (SoCG)."},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/2582112.2582152","volume-title":"30th Annual Symposium on Computational Geometry","author":"Agarwal Pankaj K.","year":"2014","unstructured":"Pankaj K. Agarwal and Jiangwei Pan. 2014. Near-linear algorithms for geometric hitting sets and set covers. In 30th Annual Symposium on Computational Geometry. ACM, 271."},{"key":"e_1_3_2_5_2","first-page":"349","volume-title":"16th International Symposium on Algorithms and Computation (ISAAC)","author":"Agarwal Pankaj K.","year":"2005","unstructured":"Pankaj K. Agarwal, Junyi Xie, Jun Yang, and Hai Yu. 2005. Monitoring continuous band-join queries over dynamic data. In 16th International Symposium on Algorithms and Computation (ISAAC). Springer, 349\u2013359."},{"key":"e_1_3_2_6_2","volume-title":"Decomposable Searching Problems","author":"Bentley Jon Louis","year":"1978","unstructured":"Jon Louis Bentley. 1978. Decomposable Searching Problems. Technical Report. Carnegie-Mellon University, Department of Computer Science."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523677"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/978-3-662-47672-7_17","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. 2015. Design of dynamic algorithms via primal-dual method. In International Colloquium on Automata, Languages, and Programming. Springer, 206\u2013218."},{"key":"e_1_3_2_9_2","article-title":"Faster approximation algorithms for geometric set cover","author":"Chan Timothy M.","year":"2020","unstructured":"Timothy M. Chan and Qizheng He. 2020. Faster approximation algorithms for geometric set cover. Symposium on Computational Geometry (SoCG) (2020).","journal-title":"Symposium on Computational Geometry (SoCG)"},{"key":"e_1_3_2_10_2","volume-title":"37th International Symposium on Computational Geometry (SoCG)","author":"Chan Timothy M.","year":"2021","unstructured":"Timothy M. Chan and Qizheng He. 2021. More dynamic data structures for geometric set cover with sublinear update time. In 37th International Symposium on Computational Geometry (SoCG)."},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"3496","DOI":"10.1137\/1.9781611977073.139","volume-title":"Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chan Timothy M.","year":"2022","unstructured":"Timothy M. Chan, Qizheng He, Subhash Suri, and Jie Xue. 2022. Dynamic geometric set cover, revisited. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 3496\u20133528."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_3_2_13_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. The MIT Press."},{"key":"e_1_3_2_14_2","first-page":"624","volume-title":"46th Annual ACM Symposium on Theory of Computing","author":"Dinur Irit","year":"2014","unstructured":"Irit Dinur and David Steurer. 2014. Analytical approach to parallel repetition. In 46th Annual ACM Symposium on Theory of Computing. ACM, 624\u2013633."},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/978-3-642-15369-3_13","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Erlebach Thomas","year":"2010","unstructured":"Thomas Erlebach and Erik Jan Van Leeuwen. 2010. PTAS for weighted set cover on unit squares. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 166\u2013177."},{"key":"e_1_3_2_16_2","volume-title":"Geometric Hitting Sets and Their Variants","author":"Ganjugunte Shashidhara K.","year":"2011","unstructured":"Shashidhara K. Ganjugunte. 2011. Geometric Hitting Sets and Their Variants. Ph. D. Dissertation. Duke University."},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1145\/3055399.3055493","volume-title":"49th Annual ACM SIGACT Symposium on Theory of Computing","author":"Gupta Anupam","year":"2017","unstructured":"Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. 2017. Online and dynamic algorithms for set cover. In 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 537\u2013550."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1024022"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90039-6"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436722"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/3115964.3116101"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3551639","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3551639","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T15:00:26Z","timestamp":1750172426000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3551639"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3551639"],"URL":"https:\/\/doi.org\/10.1145\/3551639","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2021-04-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-16","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}