{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:37Z","timestamp":1773704797454,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,7,25]],"date-time":"2017-07-25T00:00:00Z","timestamp":1500940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel Science Foundation","award":["1696\/14"],"award-info":[{"award-number":["1696\/14"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,7,25]]},"DOI":"10.1145\/3087801.3087806","type":"proceedings-article","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T17:51:38Z","timestamp":1500573098000},"page":"165-174","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Distributed Approximation of Maximum Independent Set and Maximum Matching"],"prefix":"10.1145","author":[{"given":"Reuven","family":"Bar-Yehuda","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Keren","family":"Censor-Hillel","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Zurich, Switzerland"}]},{"given":"Gregory","family":"Schwartzman","sequence":"additional","affiliation":[{"name":"Techion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2017,7,25]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581168"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.38"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1041680.1041683"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016","author":"Bar-Yehuda Reuven","year":"2016","unstructured":"Reuven Bar-Yehuda , Keren Censor-Hillel , and Gregory Schwartzman . To Appear 2016. A Distributed (2+\u03b5) -Approximation for Vertex Cover in O (log \u0394 \/ \u03b5 log log \u0394) Rounds . In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016 , Chicago, IL, USA, July 25--28 , 2016 . https:\/\/doi.org\/10.1145\/2933057.2933086 10.1145\/2933057.2933086 Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. To Appear 2016. A Distributed (2+\u03b5) -Approximation for Vertex Cover in O (log \u0394 \/ \u03b5 log log \u0394) Rounds. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25--28, 2016. https:\/\/doi.org\/10.1145\/2933057.2933086"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73101-3"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767410"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016","author":"Bodlaender Marijke HL","year":"2016","unstructured":"Marijke HL Bodlaender , Magn\u00fas M Halld\u00f3rsson , Christian Konrad , and Fabian Kuhn . To Appear 2016. Brief Announcement: Local Independent Set Approximation . In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016 , Chicago, IL, USA, July 25--28 , 2016 . Marijke HL Bodlaender, Magn\u00fas M Halld\u00f3rsson, Christian Konrad, and Fabian Kuhn. To Appear 2016. Brief Announcement: Local Independent Set Approximation. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25--28, 2016."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488665"},{"key":"e_1_3_2_1_13_1","volume-title":"9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25--28, 2003, Proceedings. 242--251","author":"Czygrinow Andrzej","year":"2003","unstructured":"Andrzej Czygrinow and Michal Hanckowiak . 2003 . Distributed Algorithm for Better Approximation of the Maximum Matching. In Computing and Combinatorics , 9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25--28, 2003, Proceedings. 242--251 . https:\/\/doi.org\/10.1007\/3--540--45071--8_26 10.1007\/3--540--45071--8_26 Andrzej Czygrinow and Michal Hanckowiak. 2003. Distributed Algorithm for Better Approximation of the Maximum Matching. In Computing and Combinatorics, 9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25--28, 2003, Proceedings. 242--251. https:\/\/doi.org\/10.1007\/3--540--45071--8_26"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_3_2_1_15_1","article-title":"Maximum matching and a polyhedron with 0, l-vertices","volume":"69","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds . 1965 a. Maximum matching and a polyhedron with 0, l-vertices . J. Res. Nat. Bur. Standards B 69 , 1965 (1965), 125--130. Jack Edmonds. 1965a. Maximum matching and a polyhedron with 0, l-vertices. J. Res. Nat. Bur. Standards B 69, 1965 (1965), 125--130.","journal-title":"J. Res. Nat. Bur. Standards B"},{"key":"e_1_3_2_1_16_1","volume-title":"trees, and flowers. Canadian Journal of mathematics 17, 3","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds . 1965b. Paths , trees, and flowers. Canadian Journal of mathematics 17, 3 ( 1965 ), 449--467. Jack Edmonds. 1965b. Paths, trees, and flowers. Canadian Journal of mathematics 17, 3 (1965), 449--467."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684464.2684469"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90055-E"},{"key":"e_1_3_2_1_20_1","volume-title":"Local Conflict Coloring. arXiv preprint arXiv:1511.01287","author":"Fraigniaud Pierre","year":"2015","unstructured":"Pierre Fraigniaud , Marc Heinrich , and Adrian Kosowski . 2015. Local Conflict Coloring. arXiv preprint arXiv:1511.01287 ( 2015 ). Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. 2015. Local Conflict Coloring. arXiv preprint arXiv:1511.01287 (2015)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_3_2_1_22_1","volume-title":"Approximation algorithms for combinatiorial optimization","author":"Halld\u00f3rsson Magn\u00fas M","unstructured":"Magn\u00fas M Halld\u00f3rsson . 1998. Approximations of independent sets in graphs . In Approximation algorithms for combinatiorial optimization . Springer , 1--13. Magn\u00fas M Halld\u00f3rsson. 1998. Approximations of independent sets in graphs. In Approximation algorithms for combinatiorial optimization. Springer, 1--13."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523693"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700381097"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548522"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"16213","key":"e_1_3_2_1_30_1","first-page":"2005","article-title":"The price of locality","author":"Kuhn Fabian","year":"2005","unstructured":"Fabian Kuhn . 2005 . The price of locality . Diss., Eidgen\u00f6ssische Technische Hochschule ETH Z\u00fcrich , Nr. 16213 , 2005 . Fabian Kuhn. 2005. The price of locality. Diss., Eidgen\u00f6ssische Technische Hochschule ETH Z\u00fcrich, Nr. 16213, 2005.","journal-title":"Diss., Eidgen\u00f6ssische Technische Hochschule ETH Z\u00fcrich"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109666"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_27"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378558"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714403"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378577"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92221-6_22"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30186-8_24"}],"event":{"name":"PODC '17: ACM Symposium on Principles of Distributed Computing","location":"Washington DC USA","acronym":"PODC '17","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087806","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3087801.3087806","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:14Z","timestamp":1750217414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087806"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,25]]},"references-count":41,"alternative-id":["10.1145\/3087801.3087806","10.1145\/3087801"],"URL":"https:\/\/doi.org\/10.1145\/3087801.3087806","relation":{},"subject":[],"published":{"date-parts":[[2017,7,25]]},"assertion":[{"value":"2017-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}