×

Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE. (English) Zbl 1458.68278

Summary: The Steiner tree problem is one of the fundamental and classical problems in combinatorial optimization. In this paper we study this problem in the CONGESTED CLIQUE model (CCM) [Z. Lotker et al., SIAM J. Comput. 35, No. 1, 120–131 (2005; Zbl 1082.05522)] of distributed computing. For the Steiner tree problem in the CCM, we consider that each vertex of the input graph is uniquely mapped to a processor and edges are naturally mapped to the links between the corresponding processors. Regarding output, each processor should know whether the vertex assigned to it is in the solution or not and which of its incident edges are in the solution. We present two deterministic distributed approximation algorithms for the Steiner tree problem in the CCM. The first algorithm computes a Steiner tree using \(\tilde{O}( n^{1 / 3})\) rounds and \(\tilde{O}( n^{7 / 3})\) messages for a given connected undirected weighted graph of \(n\) nodes. Note here that \(\tilde{O}(\cdot)\) notation hides polylogarithmic factors in \(n\). The second one computes a Steiner tree using \(O(S+\log\log n)\) rounds and \(O(Sm+ n^2)\) messages, where \(S\) and \(m\) are the shortest path diameter and number of edges respectively in the given input graph. Both the algorithms achieve an approximation ratio of \(2(1-1/\ell)\), where \(\ell\) is the number of leaf nodes in the optimal Steiner tree. For graphs with \(S=\omega( n^{1 / 3}\log n)\), the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with \(S=\tilde{o}( n^{1 / 3})\), the second algorithm outperforms the first one in terms of the round complexity. In fact when \(S=O(\log\log n)\) then the second algorithm achieves a round complexity of \(O(\log\log n)\) and message complexity of \(\tilde{O}( n^2)\). To the best of our knowledge, this is the first work to study the Steiner tree problem in the CCM.

MSC:

68W15 Distributed algorithms
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
90C27 Combinatorial optimization

Citations:

Zbl 1082.05522

Software:

MapReduce
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Berns, A., Hegeman, J. and Pemmaraju, S. V., Super-fast distributed algorithms for metric facility location, Proc. 39th Int. Colloquium on Automata, Languages, and Programming, ICALP’12 (2012), pp. 428-439. · Zbl 1367.68338
[2] Byrka, J., Grandoni, F., Rothvoß, T. and Sanità, L., An improved LP-based approximation for Steiner tree, Proc. Forty-second ACM Symposium on Theory of Computing, STOC ’10 (2010), pp. 583-592. · Zbl 1293.05039
[3] Censor-Hillel, K., Dory, M., Korhonen, J. H. and Leitersdorf, D., Fast approximate shortest paths in the congested clique, Proc. 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19 (2019), pp. 74-83. · Zbl 07298658
[4] Censor-Hillel, K., Kaski, P., Korhonen, J. H., Lenzen, C., Paz, A. and Suomela, J., Algebraic methods in the congested clique, Proc. 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15 (2015), pp. 143-152. · Zbl 1333.05283
[5] Chalermsook, P. and Fakcharoenphol, J., Simple distributed algorithms for approximating minimum Steiner trees, Proc. 11th Ann. Int. Conf. Computing and Combinatorics, COCOON ’05 (2005), pp. 380-389. · Zbl 1128.68550
[6] Chen, G.-H., Houle, M. E. and Kuo, M.-T., The Steiner problem in distributed computing systems, Inform. Sci.74(1-2) (1993) 73-96. · Zbl 0783.68041
[7] Chlebík, M. and Chlebíková, J., The Steiner tree problem on graphs: Inapproximability results, Theoret. Comput. Sci.406(3) (2008) 207-214. · Zbl 1160.68023
[8] Dean, J. and Ghemawat, S., Mapreduce: Simplified data processing on large clusters, Commun. ACM51(1) (2008) 107-113.
[9] Dolev, D., Lenzen, C. and Peled, S., “Tri, tri again”: Finding triangles and small subgraphs in a distributed setting, Proc. 26th Int. Conf. Distributed Computing, DISC ’12 (2012), pp. 195-209. · Zbl 1377.68316
[10] Drucker, A., Kuhn, F. and Oshman, R., The communication complexity of distributed task allocation, Proc. 2012 ACM Symposium on Principles of Distributed Computing, PODC ’12 (2012), pp. 67-76. · Zbl 1301.68134
[11] Drucker, A., Kuhn, F. and Oshman, R., On the power of the congested clique model, Proc. 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14 (2014), pp. 367-376. · Zbl 1321.68381
[12] Fischer, M. J. and Meyer, A. R., Boolean matrix multiplication and transitive closure, Proc. 12th Ann. Symp. Switching and Automata Theory, SWAT ’71 (1971), pp. 129-131.
[13] Gehweiler, J., Lammersen, C. and Sohler, C., A distributed \(O(1)\)-approximation algorithm for the uniform facility location problem, Algorithmica68(3) (2014) 643-670. · Zbl 1360.68893
[14] Ghaffari, M. and Parter, M., MST in log-star rounds of congested clique, Proc. 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16 (2016), pp. 19-28. · Zbl 1376.68109
[15] M. Hauptmann and M. Karpinski, A compendium on Steiner tree problems, http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.html (2015).
[16] Hegeman, J. W., Pandurangan, G., Pemmaraju, S. V., Sardeshmukh, V. B. and Scquizzato, M., Toward optimal bounds in the congested clique: Graph connectivity and MST, Proc. 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15 (2015), pp. 91-100. · Zbl 1333.68211
[17] Hegeman, J. W. and Pemmaraju, S. V., Lessons from the congested clique applied to MapReduce, Theoret. Comput. Sci.608(P3) (2015) 268-281. · Zbl 1333.68277
[18] Hegeman, J. W., Pemmaraju, S. V. and Sardeshmukh, V. B., Near-constant-time distributed algorithms on a congested clique, Proc. 28th Int. Conf. Distributed Computing, DISC’14 (2014), pp. 514-530.
[19] Holzer, S. and Pinsker, N., Approximation of distances and shortest paths in the broadcast congest clique, 19th Int. Conf. Principles of Distributed Systems, OPODIS ’15 (2015), pp. 1-16. · Zbl 1380.68428
[20] Jurdziński, T. and Nowicki, K., MST in \(O(1)\) rounds of congested clique, Proc. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18 (2018), pp. 2620-2632. · Zbl 1403.68335
[21] Karp, R. M., Reducibility among combinatorial problems, Proc. Symp. Complexity of Computer Computations (1972), pp. 85-103. · Zbl 1467.68065
[22] Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G. and Talwar, K., Efficient distributed approximation algorithms via probabilistic tree embeddings, Proc. Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC ’08 (2008), pp. 263-272. · Zbl 1301.68257
[23] Khan, M. and Pandurangan, G., A fast distributed approximation algorithm for minimum spanning trees, Distributed Comput.20(6) (2008) 391-402. · Zbl 1266.68214
[24] Klauck, H., Nanongkai, D., Pandurangan, G. and Robinson, P., Distributed computation of large-scale graph problems, Proc. Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15 (2015), pp. 391-410. · Zbl 1371.68214
[25] Kou, L., Markowsky, G. and Berman, L., A fast algorithm for Steiner trees, Acta Informatica15(2) (1981) 141-145. · Zbl 0445.68051
[26] Lenzen, C., Optimal deterministic routing and sorting on the congested clique, Proc. 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13 (2013), pp. 42-50. · Zbl 1323.68034
[27] Lenzen, C. and Patt-Shamir, B., Fast partial distance estimation and applications, Proc. 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15 (2015), pp. 153-162. · Zbl 1333.68280
[28] Linial, N., Locality in distributed graph algorithms, SIAM J. Comput.21(1) (1992) 193-201. · Zbl 0787.05058
[29] Lotker, Z., Patt-Shamir, B., Pavlov, E. and Peleg, D., Minimum-weight spanning tree construction in \(O\)(Log Log \(N)\) communication rounds, SIAM J. Comput.35(1) (2005) 120-131. · Zbl 1082.05522
[30] Munro, I., Efficient determination of the transitive closure of a directed graph, Inform. Process. Lett.1(2) (1971) 56-58. · Zbl 0221.68030
[31] Nanongkai, D., Distributed approximation algorithms for weighted shortest paths, Proc. Forty-sixth Annual ACM Symposium on Theory of Computing, STOC ’14 (2014), pp. 565-573. · Zbl 1315.05136
[32] Pai, S. and Pemmaraju, S. V., Connectivity lower bounds in broadcast congested clique, Proc. 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19 (2019), pp. 256-258. · Zbl 07298683
[33] Patt-Shamir, B. and Perry, M., Proof-labeling schemes: Broadcast, unicast and in between, Stabilization, Safety, and Security of Distributed Systems (2017), pp. 1-17. · Zbl 1498.68023
[34] Patt-Shamir, B. and Teplitsky, M., The round complexity of distributed sorting: Extended abstract, Proc. 30th Ann. ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’11 (2011), pp. 249-256. · Zbl 1321.68236
[35] Peleg, D., Distributed computing: A locality-sensitive approach, SIAM: Discr. Math. Appl. (2000). · Zbl 0959.68042
[36] Peleg, D. and Rubinovich, V., A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction, SIAM J. Comput.30(5) (2000) 1427-1442. · Zbl 0973.05074
[37] Pemmaraju, S. V. and Sardeshmukh, V. B., Super-fast MST algorithms in the congested clique using \(o(m)\) messages, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) (2016), pp. 47:1-47:15. · Zbl 1391.68119
[38] Saikia, P. and Karmakar, S., A simple \(2(1-1/\ell)\) factor distributed approximation algorithm for Steiner tree in the congest model, Proc. 20th Int. Conf. Distributed Computing and Networking, ICDCN ’19 (2019), pp. 41-50.
[39] Wu, Y. F., Widmayer, P. and Wong, C. K., A faster approximation algorithm for the Steiner problem in graphs, Acta Informatica23(2) (1986) 223-229. · Zbl 0592.68062
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.