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

announcement

Local Computation Algorithms for Graphs of Non-Constant Degrees

Authors:

Ronitt Rubinfeld,

Anak YodpinyaneeAuthors Info & Claims

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

Pages 59 - 61

https://doi.org/10.1145/2755573.2755615

Published: 13 June 2015 Publication History

Abstract

In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. This key aspect of LCAs generalizes various other models such as parallel algorithms, local filters and reconstructors. For graph problems, design techniques for LCAs and distributed algorithms are closely related and have been proven useful in each other's context. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. We consider the case where the parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in d and polylogarithmic in n; for constant eps > 0, a randomized LCA that provides a (1-ε)-approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.

References

[1]

N. Alon, R. Rubinfeld, S. Vardi, and N. Xie. Space-efficient local computation algorithms. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1132--1139. SIAM, 2012.

Digital Library

[2]

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 321--330. IEEE, 2012.

Digital Library

[3]

J. Beck. An algorithmic approach to the Lovasz local lemma. I. Random Structures & Algorithms, 2(4):343--365, 1991.

Digital Library

[4]

K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the lov--asz local lemma and graph coloring. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 134--143. ACM, 2014.

Digital Library

[5]

G. Even, M. Medina, and D. Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In Algorithms-ESA 2014, pages 394--405. Springer, 2014.

[6]

G. Even, M. Medina, and D. Ron. Distributed maximum matching in bounded degree graphs. arXiv preprint arXiv:1407.7882, 2014.

[7]

J. E. Hopcroft and R. M. Karp. An n5=2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225--231, 1973.

[8]

M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing, 15(4):1036--1053, 1986.

Digital Library

[9]

Y. Mansour and S. Vardi. A local computation approximation scheme to maximum matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 260--273. Springer, 2013.

[10]

H. N. Nguyen and K. Onak. Constant-time approximation algorithms via local improvements. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 327--336. IEEE, 2008.

Digital Library

[11]

K. Onak, D. Ron, M. Rosen, and R. Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1123--1131. SIAM, 2012.

Digital Library

[12]

M. Parnas and D. Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1):183--196, 2007.

Digital Library

[13]

O. Reingold and S. Vardi. New techniques and tighter bounds for local computation algorithms. arXiv preprint arXiv:1404.5398, 2014.

[14]

R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. Fast local computation algorithms. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7--9, 2011. Proceedings, pages 223--238, 2011.

[15]

Y. Yoshida, M. Yamamoto, and H. Ito. Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM Journal on Computing, 41(4):1074--1093, 2012.

Cited By

Behnezhad SRoghani MRubinstein ASaha BServedio R(2023)Sublinear Time Algorithms and Complexity of Approximate Maximum MatchingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585231(267-280)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585231
Bhattacharya SKiss PSaranurak T(2023)Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00095(1563-1588)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00095
Even GLevi RMedina MRosén A(2021)Sublinear Random Access Generators for Preferential Attachment GraphsACM Transactions on Algorithms10.1145/346495817:4(1-26)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3464958
Show More Cited By

Index Terms

Local Computation Algorithms for Graphs of Non-Constant Degrees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

The Randomized Local Computation Complexity of the Lovász Local Lemma
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's ...
Local Computation Algorithms for Graphs of Non-constant Degrees

In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with ...
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

We present O(loglog n) -round algorithms in the Massively Parallel Computation (MPC) model, with Õ (n) memory per machine, that compute a maximal independent set, a 1+ε approximation of maximum matching, and a 2+εapproximation of minimum vertex cover, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

June 2015

362 pages

ISBN:9781450335881

DOI:10.1145/2755573

General Chair:
Guy Blelloch
Carnegie Mellon University, USA
,
Program Chair:
Kunal Agrawal
Washington University in St. Louis, USA

Copyright © 2015 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2015

Check for updates

Author Tags

Qualifiers

Announcement

Funding Sources

Conference

SPAA '15

Sponsor:

SPAA '15: 27th ACM Symposium on Parallelism in Algorithms and Architectures

June 13 - 15, 2015

Oregon, Portland, USA

Acceptance Rates

SPAA '15 Paper Acceptance Rate 31 of 131 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
255
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Behnezhad SRoghani MRubinstein ASaha BServedio R(2023)Sublinear Time Algorithms and Complexity of Approximate Maximum MatchingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585231(267-280)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585231
Bhattacharya SKiss PSaranurak T(2023)Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00095(1563-1588)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00095
Even GLevi RMedina MRosén A(2021)Sublinear Random Access Generators for Preferential Attachment GraphsACM Transactions on Algorithms10.1145/346495817:4(1-26)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3464958
London PVardi SWierman A(2019)Logarithmic Communication for Distributed Optimization in Multi-Agent SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33666963:3(1-29)Online publication date: 17-Dec-2019
https://dl.acm.org/doi/10.1145/3366696
Czumaj AMansour YVardi S(2018)Sublinear Graph Augmentation for Fast Query ImplementationApproximation and Online Algorithms10.1007/978-3-030-04693-4_12(181-203)Online publication date: 29-Nov-2018
https://doi.org/10.1007/978-3-030-04693-4_12
London PChen NVardi SWierman A(2017)Distributed Optimization via Local Computation AlgorithmsACM SIGMETRICS Performance Evaluation Review10.1145/3152042.315205345:2(30-32)Online publication date: 11-Oct-2017
https://dl.acm.org/doi/10.1145/3152042.3152053
Rubinfeld R(2017)Can We Locally Compute Sparse Connected Subgraphs?Computer Science – Theory and Applications10.1007/978-3-319-58747-9_6(38-47)Online publication date: 6-May-2017
https://doi.org/10.1007/978-3-319-58747-9_6

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents