{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T18:42:18Z","timestamp":1730313738623,"version":"3.28.0"},"publisher-location":"New York, NY, USA","reference-count":21,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2005,7,17]]},"DOI":"10.1145\/1073814.1073835","type":"proceedings-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:31:47Z","timestamp":1123057907000},"page":"118-125","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Primal-dual based distributed algorithms for vertex cover with semi-hard capacities"],"prefix":"10.1145","author":[{"given":"F.","family":"Grandoni","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \"La Sapienza\", Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"K\u00f6nemann","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \"La Sapienza\", Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Sozio","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \"La Sapienza\", Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,7,17]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"27","article-title":"A local-ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"Bar-Yehuda R.","year":"1985","unstructured":"R. Bar-Yehuda and S. Even . A local-ratio theorem for approximating the weighted vertex cover problem . Annals of Discrete Mathematics , 25 : 27 -- 45 , 1985 . R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27--45, 1985.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_3_2_1_2_1","volume-title":"Manuscript","author":"Chudak F.","year":"2004","unstructured":"F. Chudak , T. Erlebach , and A. Panconesi . Primal-dual based distributed algorithms for vertex cover with soft capacities and facility location . Manuscript , 2004 . F. Chudak, T. Erlebach, and A. Panconesi. Primal-dual based distributed algorithms for vertex cover with soft capacities and facility location. Manuscript, 2004."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652163"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-006-1304-7"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237977"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings, International Colloquium on Automata, Languages and Processing","author":"Gandhi R.","year":"2003","unstructured":"R. Gandhi , E. Halperin , S. Khuller , G. Kortsarz , and A. Srinivasan . An improved approximation algorithm for vertex cover with hard capacities (extended abstract) . In Proceedings, International Colloquium on Automata, Languages and Processing , 2003 . R. Gandhi, E. Halperin, S. Khuller, G. Kortsarz, and A. Srinivasan. An improved approximation algorithm for vertex cover with hard capacities (extended abstract). In Proceedings, International Colloquium on Automata, Languages and Processing, 2003."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652158"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199705)10:3%3C385::AID-RSA6%3E3.0.CO;2-S"},{"key":"e_1_3_2_1_9_1","first-page":"858","volume-title":"Proceedings, ACM-SIAM Symposium on Discrete Algorithms","author":"Guha S.","year":"2002","unstructured":"S. Guha , R. Hassin , S. Khuller , and E. Or . Capacitated vertex covering with applications . In Proceedings, ACM-SIAM Symposium on Discrete Algorithms , pages 858 -- 865 , 2002 . S. Guha, R. Hassin, S. Khuller, and E. Or. Capacitated vertex covering with applications. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms, pages 858--865, 2002."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700381097"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1036"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872040"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings, ACM Symposium on Principles of Distributed Computing","author":"Jia R. Rajaraman L.","year":"2001","unstructured":"R. Rajaraman L. Jia and T. Suel . An efficient distributed algorithm for constructing small dominating sets . Proceedings, ACM Symposium on Principles of Distributed Computing , 2001 . R. Rajaraman L. Jia and T. Suel. An efficient distributed algorithm for constructing small dominating sets. Proceedings, ACM Symposium on Principles of Distributed Computing, 2001."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90033-S"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200759"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of Infocom","author":"Khaled","year":"2002","unstructured":"Khaled M. Alzoubi Peng-Jun Wan and Ophir Frieder. Distributed construction of connected dominating set in wireless ad hoc networks . Proceedings of Infocom , 2002 . Khaled M. Alzoubi Peng-Jun Wan and Ophir Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. Proceedings of Infocom, 2002."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793260763"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564602"}],"event":{"name":"PODC05: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Las Vegas NV USA","acronym":"PODC05"},"container-title":["Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1073814.1073835","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T01:13:06Z","timestamp":1673140386000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1073814.1073835"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7,17]]},"references-count":21,"alternative-id":["10.1145\/1073814.1073835","10.1145\/1073814"],"URL":"https:\/\/doi.org\/10.1145\/1073814.1073835","relation":{},"subject":[],"published":{"date-parts":[[2005,7,17]]},"assertion":[{"value":"2005-07-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}