Document Open Access Logo

Adapting Local Sequential Algorithms to the Distributed Setting

Authors Ken-ichi Kawarabayashi, Gregory Schwartzman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.35.pdf
  • Filesize: 0.48 MB
  • 17 pages

Document Identifiers

Author Details

Ken-ichi Kawarabayashi
  • National Institute of Informatics, Tokyo, Japan
Gregory Schwartzman
  • National Institute of Informatics, Tokyo, Japan

Funding

This work was supported by JST ERATO Grant Number JPMJER1201, Japan

Cite AsGet BibTex

Ken-ichi Kawarabayashi and Gregory Schwartzman. Adapting Local Sequential Algorithms to the Distributed Setting. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.35

Abstract

It is a well known fact that sequential algorithms which exhibit a strong "local" nature can be adapted to the distributed setting given a legal graph coloring. The running time of the distributed algorithm will then be at least the number of colors. Surprisingly, this well known idea was never formally stated as a unified framework. In this paper we aim to define a robust family of local sequential algorithms which can be easily adapted to the distributed setting. We then develop new tools to further enhance these algorithms, achieving state of the art results for fundamental problems. We define a simple class of greedy-like algorithms which we call orderless-local algorithms. We show that given a legal c-coloring of the graph, every algorithm in this family can be converted into a distributed algorithm running in O(c) communication rounds in the CONGEST model. We show that this family is indeed robust as both the method of conditional expectations and the unconstrained submodular maximization algorithm of Buchbinder et al. [Niv Buchbinder et al., 2015] can be expressed as orderless-local algorithms for local utility functions - Utility functions which have a strong local nature to them. We use the above algorithms as a base for new distributed approximation algorithms for the weighted variants of some fundamental problems: Max k-Cut, Max-DiCut, Max 2-SAT and correlation clustering. We develop algorithms which have the same approximation guarantees as their sequential counterparts, up to a constant additive epsilon factor, while achieving an O(log^* n) running time for deterministic algorithms and O(epsilon^{-1}) running time for randomized ones. This improves exponentially upon the currently best known algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed
  • Approximation Algorithms
  • Derandomization
  • Max-Cut

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation clustering in data streams. In ICML, volume 37 of JMLR Workshop and Conference Proceedings, pages 2237-2246. JMLR.org, 2015. Google Scholar
  2. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1-23:27, 2008. Google Scholar
  3. Per Austrin. Balanced max 2-sat might not be the hardest. In STOC, pages 189-197. ACM, 2007. Google Scholar
  4. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. In FOCS, page 238. IEEE Computer Society, 2002. Google Scholar
  5. Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In PODC, pages 165-174. ACM, 2017. Google Scholar
  6. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2 + ε)-approximation for vertex cover in o(log Δ / ε log log Δ) rounds. J. ACM, 64(3):23:1-23:11, 2017. Google Scholar
  7. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532-563, 2007. Google Scholar
  8. Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized distributed algorithms. CoRR, abs/1807.04900, 2018. URL: http://arxiv.org/abs/1807.04900.
  9. Allan Borodin, Morten N. Nielsen, and Charles Rackoff. (incremental) priority algorithms. In SODA, pages 752-761. ACM/SIAM, 2002. Google Scholar
  10. Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput., 44(5):1384-1402, 2015. URL: http://dx.doi.org/10.1137/130929205.
  11. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In PODC, pages 217-226. ACM, 2016. Google Scholar
  12. Keren Censor-Hillel, Rina Levy, and Hadas Shachnai. Fast distributed approximation for max-cut. In Algorithms for Sensor Systems, 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers, volume 10718 of Lecture Notes in Computer Science, pages 41-56. Springer, 2017. Google Scholar
  13. Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71(3):360-383, 2005. Google Scholar
  14. Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In STOC, pages 219-228. ACM, 2015. Google Scholar
  15. Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theor. Comput. Sci., 361(2-3):172-187, 2006. Google Scholar
  16. Uriel Feige and Michel X. Goemans. Aproximating the value of two prover proof systems, with applications to MAX 2sat and MAX DICUT. In ISTCS, pages 182-189. IEEE Computer Society, 1995. Google Scholar
  17. Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In FOCS, pages 180-191. IEEE Computer Society, 2017. Google Scholar
  18. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5(1):66-77, 1983. Google Scholar
  19. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified np-complete graph problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90059-1.
  20. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. CoRR, abs/1711.02194, 2017. Google Scholar
  21. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In STOC, pages 784-797. ACM, 2017. Google Scholar
  22. Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. Theory of Computing, 2(13):249-266, 2006. Google Scholar
  23. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. URL: http://dx.doi.org/10.1145/227683.227684.
  24. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  25. Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Large cuts with local algorithms on triangle-free graphs. CoRR, abs/1402.2543, 2014. Google Scholar
  26. Satyen Kale and C. Seshadhri. Combinatorial approximation algorithms for maxcut using random walks. In ICS, pages 367-388. Tsinghua University Press, 2011. Google Scholar
  27. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  28. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable csps? SIAM J. Comput., 37(1):319-357, 2007. Google Scholar
  29. Fabian Kuhn. Weak graph colorings: distributed algorithms and applications. In SPAA, pages 138-144. ACM, 2009. Google Scholar
  30. Reut Levi and Moti Medina. A (centralized) local guide. Bulletin of EATCS, 2(122), 2017. Google Scholar
  31. Michael Lewin, Dror Livnat, and Uri Zwick. Improved rounding techniques for the MAX 2-sat and MAX DI-CUT problems. In IPCO, volume 2337 of Lecture Notes in Computer Science, pages 67-82. Springer, 2002. Google Scholar
  32. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. Google Scholar
  33. Shiro Matuura and Tomomi Matsui. 0.863-approximation algorithm for MAX DICUT. In RANDOM-APPROX, volume 2129 of Lecture Notes in Computer Science, pages 138-146. Springer, 2001. Google Scholar
  34. Matthias Poloczek, Georg Schnitger, David P. Williamson, and Anke van Zuylen. Greedy algorithms for the maximum satisfiability problem: Simple algorithms and inapproximability bounds. SIAM J. Comput., 46(3):1029-1061, 2017. Google Scholar
  35. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In ICS, pages 223-238. Tsinghua University Press, 2011. Google Scholar
  36. Chaitanya Swamy. Correlation clustering: maximizing agreements via semidefinite programming. In SODA, pages 526-527. SIAM, 2004. Google Scholar
  37. Luca Trevisan. Max cut and the smallest eigenvalue. SIAM J. Comput., 41(6):1769-1786, 2012. Google Scholar
  38. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM J. Comput., 29(6):2074-2097, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact