{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:41Z","timestamp":1773704801751,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1217338 and CNS-1318294"],"award-info":[{"award-number":["CCF-1217338 and CNS-1318294"]}]},{"name":"US-Israel Binational Science Foundation"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","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":[[2015,11,2]]},"abstract":"<jats:p>\n            We present distributed network algorithms to compute weighted and unweighted matchings with improved approximation ratios and running times. The computational model is a network of processors exchanging\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            )-bit messages (the CONGEST model). For unweighted graphs, we give an algorithm providing (1-\u03f5)-approximation in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time for any constant \u03f5&gt;0, improving on the classical \u00bd-approximation in\n            <jats:italic>O<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time of Israeli and Itai [1986]. The time complexity of the algorithm depends on 1\u2043\u03f5 exponentially in the general case, and polynomially in bipartite graphs. For weighted graphs, we present another algorithm which provides (\u00bd-\u03f5) approximation in general graphs in\n            <jats:italic>O<\/jats:italic>\n            (log\u03f5\n            <jats:sup>-1<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time, improving on the previously known algorithms which attain (\u00bc-\u03f5)-approximation in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time or \u00bd-approximation in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) time. All our algorithms are randomized: the complexity bounds hold both with high probability and for the expected running time.\n          <\/jats:p>","DOI":"10.1145\/2786753","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["Improved Distributed Approximate Matching"],"prefix":"10.1145","volume":"62","author":[{"given":"Zvi","family":"Lotker","sequence":"first","affiliation":[{"name":"Ben Gurion University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","volume-title":"Spencer","author":"Alon Noga","year":"2000","unstructured":"Noga Alon and Joel H . Spencer . 2000 . The Probabilistic Method (2nd Ed.). Wiley . Noga Alon and Joel H. Spencer. 2000. The Probabilistic Method (2nd Ed.). Wiley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/161541.161736"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.72"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756869.1756904"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_24"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX). 14--23","author":"Doratha","unstructured":"Doratha E. Drake and Stefan Hougardy. 2003. Improved linear time approximation algorithms for weighted matchings . In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX). 14--23 . Doratha E. Drake and Stefan Hougardy. 2003. Improved linear time approximation algorithms for weighted matchings. In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX). 14--23."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_2_1_11_1","unstructured":"Ran Duan Seth Pettie and Hsin-Hao Su. 2015. Scaling algorithms for weighted matching in general graphs. CoRR abs\/1411.1919v2.  Ran Duan Seth Pettie and Hsin-Hao Su. 2015. Scaling algorithms for weighted matching in general graphs. CoRR abs\/1411.1919v2."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684464.2684469"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90055-E"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301360"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.8"},{"key":"e_1_2_1_16_1","unstructured":"Jaap-Henk Hoepman. 2004. Simple distributed weighted matchings. CoRR cs.DC\/0410047.  Jaap-Henk Hoepman. 2004. Simple distributed weighted matchings. CoRR cs.DC\/0410047."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780823_10"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.03.005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22148"},{"key":"e_1_2_1_22_1","volume-title":"Mathematical Issues of Production Control.","author":"Karzanov Alexander V.","unstructured":"Alexander V. Karzanov . 1973. On finding maximum flows in networks with special structure and some applications {in Russian} . In Mathematical Issues of Production Control. Vol. 5 . Moscow State University Press , 81--94. English translation available from the author's website. Alexander V. Karzanov. 1973. On finding maximum flows in networks with special structure and some applications {in Russian}. In Mathematical Issues of Production Control. Vol. 5. Moscow State University Press, 81--94. English translation available from the author's website."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0127-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109666"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378558"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714403"},{"key":"e_1_2_1_28_1","volume-title":"Plummer","author":"Lov\u00e1sz Laszlo","year":"1986","unstructured":"Laszlo Lov\u00e1sz and Michael D . Plummer . 1986 . Matching Theory. North Holland, Amsterdam . Laszlo Lov\u00e1sz and Michael D. Plummer. 1986. Matching Theory. North Holland, Amsterdam."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_30_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Mansour Yishay","unstructured":"Yishay Mansour and Shai Vardi . 2013. A local computation approximation scheme to maximum matching . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 260--273. Yishay Mansour and Shai Vardi. 2013. A local computation approximation scheme to maximum matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 260--273."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.769767"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400863.1400880"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.12.003"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.05.007"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). 223--238","author":"Rubinfeld Ronitt","year":"2011","unstructured":"Ronitt Rubinfeld , Gil Tamir , Shai Vardi , and Ning Xie . 2011 . Fast local computation algorithms . In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). 223--238 . Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. 2011. Fast local computation algorithms. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). 223--238."},{"key":"e_1_2_1_39_1","unstructured":"Vijay Vazirani. 2012. An improved definition of blossoms and a simpler proof of the MV matching algorithm. CoRR abs\/1210.4594.  Vijay Vazirani. 2012. An improved definition of blossoms and a simpler proof of the MV matching algorithm. CoRR abs\/1210.4594."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 18th International Conference on Distributed Computing (DISC'04)","author":"Wattenhofer M.","unstructured":"M. Wattenhofer and R. Wattenhofer . 2004. Distributed weighted matching . In Proceedings of the 18th International Conference on Distributed Computing (DISC'04) ). 335--348. M. Wattenhofer and R. Wattenhofer. 2004. Distributed weighted matching. In Proceedings of the 18th International Conference on Distributed Computing (DISC'04)). 335--348."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786753","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2786753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:39Z","timestamp":1750223259000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2786753"],"URL":"https:\/\/doi.org\/10.1145\/2786753","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}