nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Fast Distributed Approximation for Max-Cut

verfasst von : Keren Censor-Hillel, Rina Levy, Hadas Shachnai

Erschienen in: Algorithms for Sensor Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Finding a maximum cut is a fundamental task in many computational settings, with a central application in wireless networks. Surprisingly, Max-Cut has been insufficiently studied in the classic distributed settings, where vertices communicate by synchronously sending messages to their neighbors according to the underlying graph, known as the \(\mathcal {LOCAL}\) or \(\mathcal {CONGEST}\) models. We amend this by obtaining almost optimal algorithms for Max-Cut on a wide class of graphs in these models. In particular, for any \(\epsilon > 0\), we develop randomized approximation algorithms achieving a ratio of \((1-\varepsilon )\) to the optimum for Max-Cut on bipartite graphs in the \(\mathcal {CONGEST}\) model, and on general graphs in the \(\mathcal {LOCAL}\) model.

We further present efficient deterministic algorithms, including a 1/3-approximation for Max-Dicut in our models, thus improving the best known (randomized) ratio of 1/4. Our algorithms make non-trivial use of the greedy approach of Buchbinder et al. (SIAM Journal Computing 44:1384–1402, 2015) for maximizing an unconstrained (non-monotone) submodular function, which may be of independent interest.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks

Nächstes Kapitel Barrier Coverage with Uniform Radii in 2D

Max-Cut naturally arises also in VLSI [9], statistical physics [4] and machine learning [47].

In Max-Dicut we seek the maximum size edge-set crossing from S to \(\bar{S}\).

Due to space constraints, some of the results are omitted. A detailed version of this paper can be found in [8].

This assumption is needed only for the \((\varDelta +1)\)-coloring algorithm [6] used in Sect. 4; it can be omitted (see [6]), increasing the running time by a constant factor.

Our algorithm can be viewed as one phase of the distributed algorithm presented by Elkin et al. in [12] with some necessary changes.

This can be done by running a BFS in parallel from all vertices. Each vertex propagates the information from the root with lowest id it knows so far, and joins its tree. Thus, at the end of the process, we have a BFS tree rooted at the vertex with the lowest id.

Åstrand, M., Floréen, P., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: A local 2-approximation algorithm for the vertex cover problem. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 191–205. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04355-0_21 CrossRef

Åstrand, M., Suomela, J.: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In: Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 294–302. ACM (2010)

Bar-Yehuda, R., Censor-Hillel, K., Schwartzman, G.: A distributed (2+\(\epsilon \))-approximation for vertex cover in O(log\(\varDelta \)/\(\epsilon \) log log \(\varDelta \)) rounds. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, 25–28 July 2016, pp. 3–8 (2016)

Barahona, F., Grötschel, M., Jünger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493–513 (1988)CrossRefMATH

da Ponte Barbosa, R., Ene, A., Nguyen, H.L., Ward, J.: A new framework for distributed submodular maximization. arXiv preprint http://arxiv.org/abs/1507.03719 (2015)

Barenboim, L.: Deterministic (\(\delta \)+ 1)-coloring in sublinear (in \(\delta \)) time in static, dynamic and faulty networks. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 345–354. ACM (2015)

Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384–1402 (2015)MathSciNetCrossRefMATH

Censor-Hillel, K., Levy, R., Shachnai, H.: Fast distributed approximation for max-cut. arXiv preprint http://arxiv.org/abs/1707.08496 (2017)

Chang, K., Du, D.C.: Efficient algorithms for layer assignment problem. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 6(1), 67–78 (1987)CrossRef

10.

Chin, K.W., Soh, S., Meng, C.: Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks. Comput. Netw. 56(4), 1200–1214 (2012)CrossRef

11.

Elkin, M.: Distributed approximation: a survey. ACM SIGACT News 35(4), 40–57 (2004)CrossRef

12.

Elkin, M., Neiman, O.: Distributed strong diameter network decomposition. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 211–216. ACM (2016)

13.

Elkin, M., Neiman, O.: Efficient algorithms for constructing very sparse spanners and emulators. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, 16–19 January, pp. 652–669 (2017)

14.

Feige, U., Mirrokni, V.S., Vondrák, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011)MathSciNetCrossRefMATH

15.

Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237–267 (1976)MathSciNetCrossRefMATH

16.

Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 1–15. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41527-2_1 CrossRef

17.

Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)MathSciNetCrossRefMATH

18.

Grötschel, M., Pulleyblank, W.R.: Weakly bipartite graphs and the max-cut problem. Oper. Res. Lett. 1(1), 23–27 (1981)MathSciNetCrossRefMATH

19.

Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221–225 (1975)MathSciNetCrossRefMATH

20.

Håstad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798–859 (2001)MathSciNetCrossRefMATH

21.

Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pp. 489–498. ACM (2016)

22.

Hirvonen, J., Rybicki, J., Schmid, S., Suomela, J.: Large cuts with local algorithms on triangle-free graphs. arXiv preprint arXiv:1402.2543 (2014)

23.

Kale, S., Seshadhri, C.: Combinatorial approximation algorithms for maxcut using random walks. arXiv preprint arXiv:1008.3938 (2010)

24.

Kapralov, M., Khanna, S., Sudan, M.: Streaming lower bounds for approximating max-cut. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1263–1282. SIAM (2015)

25.

Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Springer, Heidelberg (1972). https://doi.org/10.1007/978-1-4684-2001-2_9

26.

Khot, S., Kindler, G., Mossel, E., O’Donnell, R.: Optimal inapproximability results for max-cut and other 2-variable CSPs? SIAM J. Comput. 37(1), 319–357 (2007)MathSciNetCrossRefMATH

27.

Komurlu, C., Bilgic, M.: Active inference and dynamic Gaussian Bayesian networks for battery optimization in wireless sensor networks. In: AI for Smart Grids and Smart Buildings, Papers from the 2016 AAAI Workshop, Phoenix, Arizona, USA (2016)

28.

Kuhn, F., Moscibroda, T.: Distributed approximation of capacitated dominating sets. Theory Comput. Syst. 47(4), 811–836 (2010)MathSciNetCrossRefMATH

29.

Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM (JACM) 63(2), 17 (2016)MathSciNetCrossRef

30.

Lenzen, C., Pignolet, Y.A., Wattenhofer, R.: Distributed minimum dominating set approximations in restricted families of graphs. Distrib. Comput. 26(2), 119–137 (2013)CrossRefMATH

31.

Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)MathSciNetCrossRefMATH

32.

Lotker, Z., Patt-Shamir, B., Pettie, S.: Improved distributed approximate matching. In: Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, pp. 129–136. ACM (2008)

33.

Matuura, S., Matsui, T.: 0.863-approximation algorithm for MAX DICUT. In: Goemans, M., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX/RANDOM -2001. LNCS, vol. 2129, pp. 138–146. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44666-4_17 CrossRef

34.

Miller, G.L., Peng, R., Xu, S.C.: Parallel graph decompositions using random shifts. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 196–203. ACM (2013)

35.

Mirrokni, V., Zadimoghaddam, M.: Randomized composable core-sets for distributed submodular maximization. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 153–162. ACM (2015)

36.

Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization: identifying representative elements in massive data. In: Advances in Neural Information Processing Systems, pp. 2049–2057 (2013)

37.

Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)

38.

Motwani, R., Raghavan, P.: Randomized Algorithms. Chapman & Hall/CRC, London (2010)

39.

Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 565–573. ACM (2014)

40.

Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 229–234. ACM (1988)

41.

Peleg, D.: Distributed Computing. SIAM Monographs on Discrete Mathematics and Applications, vol. 5 (2000)

42.

Sahni, S., Gonzalez, T.: P-complete approximation problems. J. ACM (JACM) 23(3), 555–565 (1976)MathSciNetCrossRefMATH

43.

Saurabh, S., Zehavi, M.: \((k,n-k)\)-Max-Cut: an \({\cal{O}}^*(2^p)\)-time algorithm and a polynomial kernel. In: Kranakis, E., Navarro, G., Chávez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 686–699. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49529-2_51 CrossRef

44.

Tangwongsan, K.: Efficient parallel approximation algorithms. Ph.D. thesis, School of Computer Science, Carnegie Mellon University (2011)

45.

Trevisan, L.: Max cut and the smallest eigenvalue. SIAM J. Comput. 41(6), 1769–1786 (2012)MathSciNetCrossRefMATH

46.

Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074–2097 (2000)MathSciNetCrossRefMATH

47.

Wang, J., Jebara, T., Chang, S.F.: Semi-supervised learning using greedy max-cut. J. Mach. Learn. Res. 14(Mar), 771–800 (2013)

48.

Wang, L., Chin, K., Soh, S.: Joint routing and scheduling in multi-Tx/Rx wireless mesh networks with random demands. Comput. Netw. 98, 44–56 (2016)CrossRef

49.

Wang, W., Liu, B., Yang, M., Luo, J., Shen, X.: Max-cut based overlapping channel assignment for 802.11 multi-radio wireless mesh networks. In: 2013 IEEE 17th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 662–667 (2013)

50.

Xu, Y., Chin, K., Raad, R., Soh, S.: A novel distributed max-weight link scheduler for multi-transmit/receive wireless mesh networks. IEEE Trans. Veh. Technol. 65(11), 9345–9357 (2016)CrossRef

51.

Xue, G., He, Q., Zhu, H., He, T., Liu, Y.: Sociality-aware access point selection in enterprise wireless LANs. IEEE Trans. Parallel Distrib. Syst. 24(10), 2069–2078 (2013)CrossRef

Titel: Fast Distributed Approximation for Max-Cut
verfasst von: Keren Censor-Hillel
Rina Levy
Hadas Shachnai
Verlag: Springer International Publishing
Buch: Algorithms for Sensor Systems
Print ISBN: 978-3-319-72750-9

Electronic ISBN: 978-3-319-72751-6

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-72751-6_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner