More Web Proxy on the site http://driver.im/

research-article

Public Access

Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints

Authors:

Sudipto GuhaAuthors Info & Claims

ACM Transactions on Parallel Computing (TOPC), Volume 4, Issue 4

Article No.: 17, Pages 1 - 40

https://doi.org/10.1145/3154855

Published: 03 January 2018 Publication History

Abstract

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 m 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.

We focus on weighted nonbipartite maximum matching in this article. For any constant p > 1, we provide an iterative sampling-based algorithm for computing a (1 − ε)-approximation of the weighted nonbipartite maximum matching that uses O(p/ε) rounds of sampling, and O(n^1+1/p) space. The results extend to b-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.

References

[1]

K. J. Ahn and S. Guha. 2013. Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput., ICALP 2011 Special Issue 222 (2013), 59--79.

Digital Library

[2]

K. J. Ahn and S. Guha. 2014. Near linear time approximation schemes for uncapacitated and capacitated --Matching problems in nonbipartite graphs. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA’14), also at Arxiv 1307.4355 (2014), 239--258.

Digital Library

[3]

K. J. Ahn, S. Guha, and A. McGregor. 2012a. Analyzing graph structure via linear measurements. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 459--467.

Digital Library

[4]

K. J. Ahn, S. Guha, and A. McGregor. 2012b. Graph sketches: Sparsification, spanners and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’12). 5--14.

Digital Library

[5]

S. Arora, E. Hazan, and S. Kale. 2012. The multiplicative weights update method: A meta algorithm and applications. Theor. Comput. 8, 6 (2012), 121--164.

[6]

B. Bahmani, A. Goel, and K. Munagala. 2014. Efficient primal dual algorithms for MapReduce. In Proceedings of the 11th International Workshop on Algorithms and Models of the Web Graph. 59--78.

[7]

A. A. Benczúr and D. R. Karger. 1996. Approximating s-t minimum cuts in time. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC’96). 47--55.

Digital Library

[8]

A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi. 2007. An Gomory-Hu tree construction algorithm for unweighted graphs. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing (STOC’07).

Digital Library

[9]

D. Bienstock and G. Iyengar. 2004. Solving fractional packing problems in O<sup>*</sup>(1+&epsi;) iterations. In Proceedings of the 36th Annual ACM Symposium on the Theory of Computing (STOC’04). 146--155.

Digital Library

[10]

A. Drucker, F. Kuhn, and R. Oshman. 2014. On the power of the congested clique model. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’14). 367--376.

Digital Library

[11]

R. Duan and S. Pettie. 2010. Approximating maximum weight matching in near-linear time. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS’10). 673--682.

Digital Library

[12]

S. Eggert, L. Kliemann, and A. Srivastav. 2009. Bipartite graph matchings in the semi-streaming model. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA’09). 492--503.

[13]

L. Epstein, A. Levin, J. Mestre, and D. Segev. 2010. Improved approximation guarantees for weighted matching in the semi-streaming model. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10). 347--358.

[14]

J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. 2005. On graph problems in a semi-streaming model. Theor. Comput. Sci. 348, 2--3 (2005), 207--216.

Digital Library

[15]

D. Foster and R. Vohra. 1999. Regret in the on-line decision problem. Games Econ. Behav. 29 (1999), 7--35.

[16]

W. S. Fung, R. Hariharan, N. J. A. Harvey, and D. Panigrahi. 2011. A general framework for graph sparsification. In Proceedings of the 43th Annual ACM Symposium on the Theory of Computing (STOC’11). 71--80.

Digital Library

[17]

M. D. Grigoriadis and L. G. Khachiyan. 1995. A sublinear-time randomized approximation algorithm for matrix games. Oper. Res. Lett. 18 (1995), 53--58.

Digital Library

[18]

V. Guruswami and K. Onak. 2013. Superlinear lower bounds for multipass graph processing. Electronic Colloquium on Computational Complexity (ECCC) 20, 2 (2013).

[19]

R. Hariharan, T. Kavitha, and D. Panigrahi. 2007. Efficient algorithms for computing all low s-t edge connectivities and related problems. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA’07).

Digital Library

[20]

M. Kapralov. 2013. Better bounds for matchings in the streaming model. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA’13). 1679--1697.

Digital Library

[21]

L. G. Khachiyan. 1978. Convergence rate of the game processes for solving matrix games. Zh. Vychisl. Mat. and Mat. Fiz. 17 (1977): 1421--1431. English translation in USSR Comput. Math and Math. Phys. 17 (1978): 78--88.

[22]

P. N. Klein and N. E. Young. 1999. On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. In Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization (IPCO’99). 320--327.

Digital Library

[23]

S. Lattanzi, B. Moseley, S. Suri, and S. Vassilvitskii. 2011. Filtering: A method for solving graph problems in MapReduce. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’11). 85--94.

Digital Library

[24]

N. Littlestone and M. M. Warmuth. 1994. The weighted majority algorithm. Inf. Comput. 108 (1994), 212--261.

Digital Library

[25]

M. Luby and N. Nisan. 1993. A parallel approximation algorithm for positive linear programming. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC’93). 448--457.

Digital Library

[26]

Y. Mansour and S. Vardi. 2013. A local computation approximation scheme to maximum matching. In Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’13). 260--273.

[27]

A. McGregor. 2005. Finding graph matchings in data streams. In Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’05). 170--181.

Digital Library

[28]

H. Nagamochi and T. Ibaraki. 1992. A linear-time algorithm for finding a sparse -connected spanning subgraph of a -connected graph. Algorithmica 7, 1--6 (1992), 583--596.

[29]

A. Nemirovski. 2005. Prox-method with rate O(1/t) of convergence for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 1 (2005), 229--251.

Digital Library

[30]

Y. Nesterov. 2005. Smooth minimization of non-smooth functions. Math. Program., Ser. A 103 (2005), 127--152.

Digital Library

[31]

M. W. Padberg and M. R. Rao. 1982. Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7, 1 (1982), 67--80.

Digital Library

[32]

S. A. Plotkin, D. B. Shmoys, and É. Tardos. 1995. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20 (1995), 257--301.

Digital Library

[33]

A. Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Algorithms and Combinatorics, Vol. 24. Springer.

[34]

M. Zelke. 2008. Weighted matching in the semi-streaming model. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS’08). 669--680.

Cited By

Czumaj AMishra GMukherjee AKuznetsov PGelles ROlivetti D(2024)Streaming Graph Algorithms in the Massively Parallel Computation ModelProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662770(496-507)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662770
Assadi SKonrad CNaidu KSundaresan JMohar BShinkar IO'Donnell R(2024)O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent SetProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649763(847-858)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649763
Feldman MSzarf A(2024)Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream ModelAlgorithmica10.1007/s00453-023-01190-486:4(1173-1209)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-023-01190-4
Show More Cited By

Index Terms

Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Matchings and factors
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

In this paper 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 m and the access to input data is constrained. These questions ...
Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded

We determine the maximum number of edges that a claw-free graph can have, when its maximum degree and matching number are bounded. This is a famous problem that has been studied on general graphs, and for which there is a tight bound. The graphs ...
Forbidden subgraphs and the König-Egerváry property

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the Konig-Egervary property if its matching number equals its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Parallel Computing

ACM Transactions on Parallel Computing Volume 4, Issue 4

Special Issue on SPAA 2015

December 2017

122 pages

ISSN:2329-4949

EISSN:2329-4957

DOI:10.1145/3177741

Editor:
Phillip B. Gibbons
Carnegie Mellon University, Pittsburgh, USA

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 2018

Accepted: 01 September 2017

Revised: 01 August 2017

Received: 01 July 2016

Published in TOPC Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
417
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)6

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Czumaj AMishra GMukherjee AKuznetsov PGelles ROlivetti D(2024)Streaming Graph Algorithms in the Massively Parallel Computation ModelProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662770(496-507)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662770
Assadi SKonrad CNaidu KSundaresan JMohar BShinkar IO'Donnell R(2024)O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent SetProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649763(847-858)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649763
Feldman MSzarf A(2024)Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream ModelAlgorithmica10.1007/s00453-023-01190-486:4(1173-1209)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-023-01190-4
Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
https://dl.acm.org/doi/10.1145/3623800.3623808
Assadi SBehnezhad SKhanna SLi HSaha BServedio R(2023)On Regularity Lemma and Barriers in Streaming and Dynamic MatchingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585110(131-144)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585110
Assadi SSundaresan J(2023)Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00058(909-932)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00058
Fischer MMitrović SUitto JLeonardi SGupta A(2022)Deterministic (1+𝜀)-approximate maximum matching with poly(1/𝜀) passes in the semi-streaming model and beyondProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520039(248-260)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520039
Fernando RGelles YKomargodski IShi E(2022)Maliciously Secure Massively Parallel Computation for All-but-One CorruptionsAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_24(688-718)Online publication date: 12-Oct-2022
https://doi.org/10.1007/978-3-031-15802-5_24
Charikar MMa WTan LScheideler CSpear M(2020)Unconditional Lower Bounds for Adaptive Massively Parallel ComputationProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400230(141-151)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400230
Chung KHo KSun XScheideler CSpear M(2020)On the Hardness of Massively Parallel ComputationProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400223(153-162)Online publication date: 9-Jul-2020
https://doi.org/10.1145/3350755.3400223
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents