Distributed approximation of maximum independent set and maximum matching. (English) Zbl 1380.68416
Proceedings of the 2017 ACM symposium on principles of distributed computing, PODC ’17, Washington, DC, USA, July 25–27, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4992-5). 165-174 (2017).
MSC:
| 68W15 | Distributed algorithms |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W25 | Approximation algorithms |
| 68W40 | Analysis of algorithms |
References:
| [1] | Noga Alon and Nabil Kahale. 1998. Approximating the independence number via the θ-function. Mathematical Programming 80, 3 (1998), 253-264. 10.1007/BF01581168 · Zbl 0895.90169 |
| [2] | Per Austrin, Subhash Khot, and Muli Safra. 2009. Inapproximability of vertex cover and independent set in bounded degree graphs. In Computational Complexity, 2009. CCC’09. 24th Annual IEEE Conference on. IEEE, 74-80. 10.1109/CCC.2009.38 · Zbl 1243.68183 |
| [3] | Nikhil Bansal. 2015. Approximating independent sets in sparse graphs. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1-8. 10.1137/1.9781611973730.1 · Zbl 1372.68295 |
| [4] | Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. 2001. A unified approach to approximating resource allocation and scheduling. Journal of the ACM (JACM) 48, 5 (2001), 1069-1090. 10.1145/502102.502107 · Zbl 1323.68564 |
| [5] | Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. 2004. Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon even 1935-2004. ACM Computing Surveys (CSUR) 36, 4 (2004), 422-463. 10.1145/1041680.1041683 · Zbl 1181.90109 |
| [6] | Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. To Appear 2016. A Distributed (2+ε) -Approximation for Vertex Cover in O (log Δ / ε log log Δ) Rounds. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016. https://doi.org/10.1145/2933057.2933086 · Zbl 1376.68155 |
| [7] | Reuven Bar-Yehuda and Shimon Even. 1985. A local-ratio theorem for approximating the weighted vertex cover problem. North-Holland Mathematics Studies 109 (1985), 27-45. 10.1016/S0304-0208(08)73101-3 · Zbl 0545.90074 |
| [8] | Leonid Barenboim. 2015. Deterministic \((Δ +1)\)-Coloring in Sublinear (in(Δ)\) Time in Static, Dynamic and Faulty Networks. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, Chryssis Georgiou and Paul G. Spirakis (Eds.). ACM, 345-354. x978-1-4503-3617-8 https://doi.org/10.1145/2767386.2767410 · Zbl 1333.68202 |
| [9] | Leonid Barenboim, Michael Elkin, and Fabian Kuhn. 2014. Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput. 43, 1 (2014), 72-95. https://doi.org/10.1137/12088848X 10.1137/12088848X · Zbl 1311.68185 |
| [10] | Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2016. The Locality of Distributed Symmetry Breaking. J. ACM 63, 3 (2016), 20:1-20:45. https://doi.org/10.1145/2903137 · Zbl 1426.68020 |
| [11] | Marijke HL Bodlaender, Magnús M Halldórsson, Christian Konrad, and Fabian Kuhn. To Appear 2016. Brief Announcement: Local Independent Set Approximation. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016. · Zbl 1376.68156 |
| [12] | Siu On Chan. 2013. Approximation resistance from pairwise independent subgroups. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing. ACM, 447-456. 10.1145/2488608.2488665 · Zbl 1293.68163 |
| [13] | Andrzej Czygrinow and Michal Hanckowiak. 2003. Distributed Algorithm for Better Approximation of the Maximum Matching. In Computing and Combinatorics, 9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25-28, 2003, Proceedings. 242-251. https://doi.org/10.1007/3-540-45071-8_26 · Zbl 1276.05112 |
| [14] | Andrzej Czygrinow, Michal Hanćkowiak, and Wojciech Wawrzyniak. 2008. Fast distributed approximations in planar graphs. In Distributed Computing. Springer, 78-92. 10.1007/978-3-540-87779-0_6 · Zbl 1161.68865 |
| [15] | Jack Edmonds. 1965a. Maximum matching and a polyhedron with 0, l-vertices. J. Res. Nat. Bur. Standards B 69, 1965 (1965), 125-130. · Zbl 0141.21802 |
| [16] | Jack Edmonds. 1965b. Paths, trees, and flowers. Canadian Journal of mathematics 17, 3 (1965), 449-467. · Zbl 0132.20903 |
| [17] | Guy Even, Moti Medina, and Dana Ron. 2015. Distributed maximum matching in bounded degree graphs. In Proceedings of the 2015 International Conference on Distributed Computing and Networking. ACM, 18. 10.1145/2684464.2684469 |
| [18] | Uriel Feige. 2004. Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics 18, 2 (2004), 219-225. 10.1137/S089548010240415X · Zbl 1068.05052 |
| [19] | Ted Fischer, Andrew V Goldberg, David J Haglin, and Serge Plotkin. 1993. Approximating matchings in parallel. Inform. Process. Lett. 46, 3 (1993), 115-118. 10.1016/0020-0190(93)90055-E · Zbl 0784.68065 |
| [20] | Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. 2015. Local Conflict Coloring. arXiv preprint arXiv:1511.01287 (2015). |
| [21] | Mohsen Ghaffari. 2016. An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’16). SIAM, 270-277. x978-1-611974-33-1 http://dl.acm.org/citation.cfm?id=2884435.2884455 · Zbl 1411.68175 |
| [22] | Magnús M Halldórsson. 1998. Approximations of independent sets in graphs. In Approximation algorithms for combinatiorial optimization. Springer, 1-13. · Zbl 0903.05044 |
| [23] | Magnús M Halldórsson. 2000. Approximations of weighted independent set and hereditary subset problems. Journal of Graph Algorithms and Applications 4, 1 (2000), 1-16. 10.7155/jgaa.00020 · Zbl 0952.05069 |
| [24] | Magnús M Halldórsson and Jaikumar Radhakrishnan. 1997. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18, 1 (1997), 145-163. 10.1007/BF02523693 · Zbl 1344.68286 |
| [25] | Eran Halperin. 2002. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31, 5 (2002), 1608-1623. 10.1137/S0097539700381097 · Zbl 1041.68130 |
| [26] | Johan Håstad. 1996. Clique is hard to approximate within n 1-ε. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on. IEEE, 627-636. |
| [27] | John E Hopcroft and Richard M Karp. 1973. An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing 2, 4 (1973), 225-231. 10.1137/0202019 · Zbl 0253.05133 |
| [28] | David Karger, Rajeev Motwani, and Madhu Sudan. 1998. Approximate graph coloring by semidefinite programming. Journal of the ACM (JACM) 45, 2 (1998), 246-265. 10.1145/274787.274791 · Zbl 0904.68116 |
| [29] | Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York. 85-103. http://www.cs.berkeley.edu/ luca/cs172/karp.pdf 10.1007/978-1-4684-2001-2_9 · Zbl 1467.68065 |
| [30] | Fabian Kuhn. 2005. The price of locality. Diss., Eidgenössische Technische Hochschule ETH Zürich, Nr. 16213, 2005. · Zbl 1314.68160 |
| [31] | Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2006. The price of being near-sighted. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. Society for Industrial and Applied Mathematics, 980-989. 10.1145/1109557.1109666 · Zbl 1192.68044 |
| [32] | Christoph Lenzen and Roger Wattenhofer. 2008. Leveraging Linial’s locality limit. In Distributed Computing. Springer, 394-407. 10.1007/978-3-540-87779-0_27 · Zbl 1161.68344 |
| [33] | Nathan Linial. 1987. Distributive Graph Algorithms Global Solutions from Local Data. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science (SFCS ’87). IEEE Computer Society, Washington, DC, USA, 331-335. x0-8186-0807-2 https://doi.org/10.1109/SFCS.1987.20 |
| [34] | Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. 2008. Improved distributed approximate matching. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures. ACM, 129-136. 10.1145/1378533.1378558 |
| [35] | Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. 2015. Improved distributed approximate matching. Journal of the ACM (JACM) 62, 5 (2015). 10.1145/2786753 · Zbl 1426.68292 |
| [36] | Zvi Lotker, Boaz Patt-Shamir, and Adi Rosén. 2009. Distributed approximate matching. SIAM J. Comput. 39, 2 (2009), 445-460. 10.1137/080714403 · Zbl 1200.68278 |
| [37] | Michael Luby. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing 15, 4 (1986), 1036-1053. 10.1137/0215074 · Zbl 0619.68058 |
| [38] | Alessandro Panconesi and Mauro Sozio. 2008. Fast distributed scheduling via primal-dual. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures. ACM, 229-235. 10.1145/1378533.1378577 · Zbl 1267.68312 |
| [39] | Boaz Patt-Shamir, Dror Rawitz, and Gabriel Scalosub. 2008. Distributed approximation of cellular coverage. In Principles of Distributed Systems. Springer, 331-345. 10.1007/978-3-540-92221-6_22 · Zbl 1242.68025 |
| [40] | David Peleg. 2000. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. x0-89871-464-8 10.1137/1.9780898719772 · Zbl 0959.68042 |
| [41] | Mirjam Wattenhofer and Roger Wattenhofer. 2004. Distributed weighted matching. Springer. 10.1007/978-3-540-30186-8_24 · Zbl 1110.68547 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
