{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:02:25Z","timestamp":1764687745622,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T00:00:00Z","timestamp":1497571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1696\/14"],"award-info":[{"award-number":["1696\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>\n            We present a simple deterministic distributed (2 + \u03f5)-approximation algorithm for minimum-weight vertex cover, which completes in\n            <jats:italic>O<\/jats:italic>\n            (log \u0394\/\u03f5log log \u0394) rounds, where \u0394 is the maximum degree in the graph, for any \u03f5 &gt; 0 that is at most\n            <jats:italic>O<\/jats:italic>\n            (1). For a constant \u03f5, this implies a constant approximation in\n            <jats:italic>O<\/jats:italic>\n            (log \u0394\/log log \u0394) rounds, which contradicts the lower bound of [KMW10].\n          <\/jats:p>","DOI":"10.1145\/3060294","type":"journal-article","created":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T18:10:59Z","timestamp":1497636659000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["A Distributed (2 + \u03b5)-Approximation for Vertex Cover in O(log \u0394 \/ \u03b5 log log \u0394) Rounds"],"prefix":"10.1145","volume":"64","author":[{"given":"Reuven","family":"Bar-Yehuda","sequence":"first","affiliation":[{"name":"Technion Israel Institute of Technology Faculty of Computer Science"}]},{"given":"Keren","family":"Censor-Hillel","sequence":"additional","affiliation":[{"name":"Technion, Computer Science"}]},{"given":"Gregory","family":"Schwartzman","sequence":"additional","affiliation":[{"name":"Technion Israel Institute of Technology Faculty of Computer Science"}]}],"member":"320","published-online":{"date-parts":[[2017,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813164.1813191"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810533"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010009"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73101-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/050625382"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"volume-title":"An exponential separation between randomized and deterministic complexity in the LOCAL model","author":"Chang Yi-Jun","key":"e_1_2_1_9_1","unstructured":"Yi-Jun Chang , Tsvi Kopelowitz , and Seth Pettie . 2016. An exponential separation between randomized and deterministic complexity in the LOCAL model . In FOCS. IEEE Computer Society , 615--624. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. 2016. An exponential separation between randomized and deterministic complexity in the LOCAL model. In FOCS. IEEE Computer Society, 615--624."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_12_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"volume-title":"An improved distributed algorithm for maximal independent set","author":"Ghaffari Mohsen","key":"e_1_2_1_13_1","unstructured":"Mohsen Ghaffari . 2016. An improved distributed algorithm for maximal independent set . In SODA. SIAM , 270--277. Mohsen Ghaffari. 2016. An improved distributed algorithm for maximal independent set. In SODA. SIAM, 270--277."},{"volume-title":"Distributed degree splitting, edge coloring, and orientations","author":"Ghaffari Mohsen","key":"e_1_2_1_14_1","unstructured":"Mohsen Ghaffari and Hsin-Hao Su. 2017. Distributed degree splitting, edge coloring, and orientations . In SODA. SIAM , 2505--2523. Mohsen Ghaffari and Hsin-Hao Su. 2017. Distributed degree splitting, edge coloring, and orientations. In SODA. SIAM, 2505--2523."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435381"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/06065310X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1036"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0127-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109666"},{"key":"e_1_2_1_25_1","volume-title":"Local computation: Lower and upper bounds. CoRR abs\/1011.5470","author":"Kuhn Fabian","year":"2010","unstructured":"Fabian Kuhn , Thomas Moscibroda , and Roger Wattenhofer . 2010. Local computation: Lower and upper bounds. CoRR abs\/1011.5470 ( 2010 ). http:\/\/arxiv.org\/abs\/1011.5470 Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2010. Local computation: Lower and upper bounds. CoRR abs\/1011.5470 (2010). http:\/\/arxiv.org\/abs\/1011.5470"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.12.003"},{"key":"e_1_2_1_30_1","unstructured":"Seth Pettie. 2016. Personal communication.  Seth Pettie. 2016. Personal communication."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.02.017"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3060294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3060294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:20Z","timestamp":1750215800000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3060294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,16]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3060294"],"URL":"https:\/\/doi.org\/10.1145\/3060294","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2017,6,16]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}