{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T22:57:48Z","timestamp":1766012268374,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1536002, 1540541, 1617790, 1527084, 1535972"],"award-info":[{"award-number":["1536002, 1540541, 1617790, 1527084, 1535972"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055493","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"537-550","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Online and dynamic algorithms for set cover"],"prefix":"10.1145","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Ravishankar","family":"Krishnaswamy","sequence":"additional","affiliation":[{"name":"Microsoft Research, India"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[{"name":"IIT Delhi, India"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1109\/FOCS.2014.53"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1137\/060661946"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1007\/PL00009263"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1016\/0304-3975(94)90153-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.5555\/645929.672712"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1137\/130914140"},{"key":"e_1_3_2_1_7_1","first-page":"179","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I","author":"Bernstein A.","year":"2015","unstructured":"Bernstein , A. , and Stein , C . Fully dynamic matching in bipartite graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I ( 2015 ), pp. 167\u2013 179 . Bernstein, A., and Stein, C. Fully dynamic matching in bipartite graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I (2015), pp. 167\u2013179."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.5555\/2884435.2884485"},{"key":"e_1_3_2_1_9_1","volume-title":"ArXiv Pre-print dated 1st November","author":"Bhattacharya S.","year":"2016","unstructured":"Bhattacharya , S. , Chakrabarty , D. , and Henzinger , M . Deterministic fully dynamic approximate vertex cover and fractional matching in o(1) amortized update time . In ArXiv Pre-print dated 1st November ( 2016 ). Bhattacharya, S., Chakrabarty, D., and Henzinger, M. Deterministic fully dynamic approximate vertex cover and fractional matching in o(1) amortized update time. In ArXiv Pre-print dated 1st November (2016)."},{"key":"e_1_3_2_1_10_1","series-title":"Lecture Notes in Comput","first-page":"218","volume-title":"Automata, languages, and programming. Part I","author":"Bhattacharya S.","year":"2015","unstructured":"Bhattacharya , S. , Henzinger , M. , and Italiano , G. F . Design of dynamic algorithms via primal-dual method . In Automata, languages, and programming. Part I , vol. 9134 of Lecture Notes in Comput . Sci. Springer , Heidelberg, 2015 , pp. 206\u2013 218 . Bhattacharya, S., Henzinger, M., and Italiano, G. F. Design of dynamic algorithms via primal-dual method. In Automata, languages, and programming. Part I, vol. 9134 of Lecture Notes in Comput. Sci. Springer, Heidelberg, 2015, pp. 206\u2013218."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.5555\/2722129.2722183"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/2897518.2897568"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1109\/FOCS.2014.48"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1109\/INFCOM.2009.5062016"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_3_2_1_16_1","first-page":"25","volume-title":"CRC","author":"Eppstein D.","year":"1999","unstructured":"Eppstein , D. , Galil , Z. , and Italiano , G. F . Dynamic graph algorithms. In Algorithms and theory of computation handbook . CRC , Boca Raton, FL , 1999 , pp. 8\u20131\u20138\u2013 25 . Eppstein, D., Galil, Z., and Italiano, G. F. Dynamic graph algorithms. In Algorithms and theory of computation handbook. CRC, Boca Raton, FL, 1999, pp. 8\u20131\u20138\u201325."},{"key":"e_1_3_2_1_17_1","series-title":"Lecture Notes in Comput","first-page":"578","volume-title":"ESA","author":"Epstein L.","year":"2011","unstructured":"Epstein , L. , and Levin , A . Robust algorithms for preemptive scheduling . In ESA , vol. 6942 of Lecture Notes in Comput . Sci. Springer , Heidelberg, 2011 , pp. 567\u2013 578 . Epstein, L., and Levin, A. Robust algorithms for preemptive scheduling. In ESA, vol. 6942 of Lecture Notes in Comput. Sci. Springer, Heidelberg, 2011, pp. 567\u2013578."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.5555\/645930.758390"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/2488608.2488674"},{"key":"e_1_3_2_1_20_1","volume-title":"Online and dynamic algorithms for set cover. CoRR abs\/1611.05646","author":"Gupta A.","year":"2016","unstructured":"Gupta , A. , Krishnaswamy , R. , Kumar , A. , and Panigrahi , D . Online and dynamic algorithms for set cover. CoRR abs\/1611.05646 ( 2016 ). Gupta, A., Krishnaswamy, R., Kumar, A., and Panigrahi, D. Online and dynamic algorithms for set cover. CoRR abs\/1611.05646 (2016)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.5555\/2634074.2634108"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.5555\/2634074.2634109"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1109\/FOCS.2013.65"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1145\/2746539.2746609"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1137\/0404033"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.5555\/2884435.2884524"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1145\/2746539.2746615"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1007\/978-3-642-31594-7_58"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1145\/2700206"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1145\/1806689.1806753"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1007\/PL00009214"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1287\/moor.1090.0381"},{"key":"e_1_3_2_1_35_1","first-page":"126","volume-title":"SODA","author":"Sankowski P.","year":"2007","unstructured":"Sankowski , P. Faster dynamic matchings and vertex connectivity . In SODA ( 2007 ), pp. 118\u2013 126 . Sankowski, P. Faster dynamic matchings and vertex connectivity. In SODA (2007), pp. 118\u2013126."},{"key":"e_1_3_2_1_36_1","series-title":"LNCS","first-page":"47","volume-title":"ESA (I)","author":"Skutella M.","year":"2010","unstructured":"Skutella , M. , and Verschae , J . A robust PTAS for machine covering and packing . In ESA (I) , vol. 6346 of LNCS . Springer , Berlin , 2010 , pp. 36\u2013 47 . Skutella, M., and Verschae, J. A robust PTAS for machine covering and packing. In ESA (I), vol. 6346 of LNCS. Springer, Berlin, 2010, pp. 36\u201347."},{"key":"e_1_3_2_1_37_1","volume-title":"FOCS","author":"Solomon S.","year":"2016","unstructured":"Solomon , S. Fully dynamic maximal matching in constant update time . In FOCS ( 2016 ). Solomon, S. Fully dynamic maximal matching in constant update time. In FOCS (2016)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1006\/jagm.2000.1074"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.5555\/1971947"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '17","name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada"},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055493","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055493","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055493","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":37,"alternative-id":["10.1145\/3055399.3055493","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055493","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}