{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T13:21:04Z","timestamp":1762003264283,"version":"build-2065373602"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,1,18]],"date-time":"2018-01-18T00:00:00Z","timestamp":1516233600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00224-017-9842-1","type":"journal-article","created":{"date-parts":[[2018,1,18]],"date-time":"2018-01-18T07:10:47Z","timestamp":1516259447000},"page":"1763-1797","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Set Cover Problems with Small Neighborhood Covers"],"prefix":"10.1007","volume":"62","author":[{"given":"Archita","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anamitra R.","family":"Choudhury","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sambudha","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yogish","family":"Sabharwal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,18]]},"reference":[{"key":"9842_CR1","unstructured":"Agarwal, A., Chakaravarthy, V., Choudhury, A., Roy, S., Sabharwal, Y.: Distributed and parallel algorithms for set cover problems with small neighborhood covers. In: 33rd Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 249\u2013261 (2013)"},{"issue":"5","key":"9842_CR2","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069\u20131090 (2001)","journal-title":"J. ACM"},{"key":"9842_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P., DasGupta, B.: Improvements in throughout maximization for real-time scheduling. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 680\u2013687 (2000)","DOI":"10.1145\/335305.335401"},{"issue":"6","key":"9842_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0020-0190(90)90209-G","volume":"33","author":"A Bertossi","year":"1990","unstructured":"Bertossi, A., Moretti, S.: Parallel algorithms on circular-arc graphs. Inf. Process. Lett. 33(6), 275\u2013281 (1990)","journal-title":"Inf. Process. Lett."},{"key":"9842_CR5","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Kumar, A., Roy, S., Sabharwal, Y.: Resource allocation for covering time varying demands. In: Proceedings of the 19th European Symposium on Algorithms (ESA), pp. 543\u2013554 (2011)","DOI":"10.1007\/978-3-642-23719-5_46"},{"key":"9842_CR6","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Grant, E., K\u00f6nemann, J.: On column-restricted and priority covering integer programs. In: 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 365\u2013368 (2010)","DOI":"10.1007\/978-3-642-13036-6_27"},{"issue":"5","key":"9842_CR7","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129\u20131146 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9842_CR8","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"9842_CR9","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"issue":"1","key":"9842_CR10","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1145\/1435375.1435381","volume":"5","author":"F Grandoni","year":"2008","unstructured":"Grandoni, F., K\u00f6nemann, J., Panconesi, A.: Distributed weighted vertex cover via maximal matchings. ACM Transactions on Algorithms 5(1), 839\u2013848 (2008)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"9842_CR11","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.1994.1036","volume":"17","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U., Young, N.E.: A primal-dual parallel approximation technique applied to weighted set and vertex covers. J. Algorithms 17(2), 280\u2013289 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"9842_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00446-011-0127-7","volume":"24","author":"C Koufogiannakis","year":"2011","unstructured":"Koufogiannakis, C., Young, N.: Distributed algorithms for covering, packing and maximum weighted matching. Distrib. Comput. 24(1), 45\u201363 (2011)","journal-title":"Distrib. Comput."},{"key":"9842_CR13","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"issue":"4","key":"9842_CR14","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N Linial","year":"1993","unstructured":"Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica 13(4), 441\u2013454 (1993)","journal-title":"Combinatorica"},{"issue":"4","key":"9842_CR15","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9842_CR16","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00446-010-0100-x","volume":"22","author":"A Panconesi","year":"2010","unstructured":"Panconesi, A., Sozio, M.: Fast primal-dual distributed algorithms for scheduling and matching problems. Distrib. Comput. 22(4), 269\u2013283 (2010)","journal-title":"Distrib. Comput."},{"issue":"2","key":"9842_CR17","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1137\/S0097539793260763","volume":"28","author":"S Rajagopalan","year":"1998","unstructured":"Rajagopalan, S., Vazirani, V.: Primal-dual rnc approximation algorithms for set cover and covering integer programs. SIAM J. Comput. 28(2), 525\u2013540 (1998)","journal-title":"SIAM J. Comput."},{"key":"9842_CR18","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"9842_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D Williamson","year":"2011","unstructured":"Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"issue":"2","key":"9842_CR20","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2151171.2151177","volume":"8","author":"Y Ye","year":"2012","unstructured":"Ye, Y., Borodin, A.: Elimination graphs. ACM Trans. Algorithms 8(2), 14 (2012)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9842-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9842-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9842-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,18]],"date-time":"2019-01-18T01:04:46Z","timestamp":1547773486000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9842-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,18]]},"references-count":20,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9842"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9842-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2018,1,18]]},"assertion":[{"value":"18 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}