{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:13Z","timestamp":1750221373550,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,31]],"date-time":"2017-12-31T00:00:00Z","timestamp":1514678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1117216 and 1546151"],"award-info":[{"award-number":["1117216 and 1546151"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>\n            In this article, we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read-only input) is sublinear in the number of edges\n            <jats:italic>m<\/jats:italic>\n            and the access to input is constrained. These questions arise in many natural settings, and in particular in the analysis of streaming algorithms, MapReduce or similar algorithms, or message passing distributed computing that model constrained parallelism with sublinear central processing.\n          <\/jats:p>\n          <jats:p>\n            We focus on weighted nonbipartite maximum matching in this article. For any constant\n            <jats:italic>p<\/jats:italic>\n            &gt; 1, we provide an iterative sampling-based algorithm for computing a (1 \u2212 \u03b5)-approximation of the weighted nonbipartite maximum matching that uses\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>p<\/jats:italic>\n            \/\u03b5) rounds of sampling, and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+1\/\n              <jats:italic>p<\/jats:italic>\n            <\/jats:sup>\n            ) space. The results extend to\n            <jats:italic>b<\/jats:italic>\n            -Matching with small changes. This article combines adaptive sketching literature and fast primal-dual algorithms based on relaxed Dantzig-Wolfe decision procedures. Each round of sampling is implemented through linear sketches and can be executed in a single round of streaming or two rounds of MapReduce. The article also proves that nonstandard linear relaxations of a problem, in particular penalty-based formulations, are helpful in reducing the adaptive dependence of the iterations.\n          <\/jats:p>","DOI":"10.1145\/3154855","type":"journal-article","created":{"date-parts":[[2018,1,4]],"date-time":"2018-01-04T16:27:31Z","timestamp":1515083251000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Access to Data and Number of Iterations"],"prefix":"10.1145","volume":"4","author":[{"given":"Kook Jin","family":"Ahn","sequence":"first","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634092"},{"volume-title":"Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Ahn K. J.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"volume-title":"Proceedings of the 11th International Workshop on Algorithms and Models of the Web Graph. 59--78","author":"Bahmani B.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250879"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007382"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.70"},{"volume-title":"Proceedings of the 17th Annual European Symposium on Algorithms (ESA\u201909)","author":"Eggert S.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910)","author":"Epstein L.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0740"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(95)00032-0"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"V. Guruswami and K. Onak. 2013. Superlinear lower bounds for multipass graph processing. Electronic Colloquium on Computational Complexity (ECCC) 20 2 (2013).  V. Guruswami and K. Onak. 2013. Superlinear lower bounds for multipass graph processing. Electronic Colloquium on Computational Complexity (ECCC) 20 2 (2013).","DOI":"10.1109\/CCC.2013.37"},{"volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Hariharan R.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627938"},{"issue":"1977","key":"e_1_2_1_21_1","first-page":"1421","article-title":"Convergence rate of the game processes for solving matrix games","volume":"17","author":"Khachiyan L. G.","year":"1978","journal-title":"Zh. Vychisl. Mat. and Mat. Fiz."},{"volume-title":"Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization (IPCO\u201999)","author":"Klein P. N.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167211"},{"volume-title":"Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201913)","author":"Mansour Y.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.67"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_2_1_33_1","volume-title":"Algorithms and Combinatorics","volume":"24","author":"Schrijver A.","year":"2003"},{"volume-title":"Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS\u201908)","year":"2008","author":"Zelke M.","key":"e_1_2_1_34_1"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154855","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154855","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154855","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:38Z","timestamp":1750213598000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154855"}},"subtitle":["Dual Primal Algorithms for Maximum Matching under Resource Constraints"],"short-title":[],"issued":{"date-parts":[[2017,12,31]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3154855"],"URL":"https:\/\/doi.org\/10.1145\/3154855","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2017,12,31]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}