Abstract
We study the NP-hard problem of approximating a Minimum Routing Cost Spanning Tree in the message passing model with limited bandwidth (CONGEST model). In this problem one tries to find a spanning tree of a graph G over n nodes that minimizes the sum of distances between all pairs of nodes. In the considered model every node can transmit a different (but short) message to each of its neighbors in each synchronous round. We provide a randomized (2 + ε)-approximation with runtime \(\mathcal{O}(D+\frac{\log n}{\varepsilon})\) for unweighted graphs. Here, D is the diameter of G. This improves over both, the (expected) approximation factor \(\mathcal{O}(\log n)\) and the runtime \(\mathcal{O}(D\log^2 n)\) stated in [13].
Due to stating our results in a very general way, we also derive an (optimal) runtime of \(\mathcal{O}(D)\) when considering \(\mathcal{O}(\log n)\)-approximations as in [13]. In addition we derive a deterministic 2-approximation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, October 14-16, pp. 184–193 (1996)
Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Vitter, J.S. (ed.) Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC 1998, Dallas, Texas, USA, May 23-26, pp. 161–168 (1998)
Campos, R., Ricardo, M.: A fast algorithm for computing minimum routing cost spanning trees. Computer Networks 52(17), 3229–3247 (2008)
Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median. In: Vitter, J.S. (ed.) Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC 1998, Dallas, Texas, USA, May 23-26, pp. 114–123 (1998)
Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM Journal on Computing 41(5), 1235–1265 (2012)
Dionne, R., Florian, M.: Exact and approximate algorithms for optimal network design. Networks 9(1), 37–59 (1979)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Larmore, L.L., Goemans, M.X. (eds.) Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC 2003, San Diego, California, USA, June 9-11, pp. 448–455 (2003)
Hochuli, A., Holzer, S., Wattenhofer, R.: Distributed approximation of minimum routing cost trees. Computing Research Repository CoRR, abs/1406.1244 (2014), http://arxiv.org/abs/1406.1244
Holzer, S., Peleg, D., Roditty, L., Tal, E., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications (2014), http://www.dcg.ethz.ch/~stholzer/APSP-full.pdf , preliminary full version of two merged papers to be submitted to a journal). New versions available on request
Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: Kowalski, D., Panconesi, A. (eds.) Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2012, Funchal, Madeira, Portugal, July 16-18, pp. 355–364 (2012)
Hu, T.C.: Optimum communication spanning trees. SIAM Journal on Computing 3(3), 188–195 (1974)
Johnson, D.S., Lenstra, J.K., Rinnooy Kan, A.H.G.: The complexity of the network design problem. Networks 8(4), 279–285 (1978)
Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. In: Bazzi, R.A., Patt-Shamir, B. (eds.) Proceedings of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Ontario, August 18-21, pp. 263–272 (2008)
Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. To appear in: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 2014, New York, USA, May 31-June 3 (2014)
Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)
Peleg, D.: Low stretch spanning trees. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 68–80. Springer, Heidelberg (2002)
Reshef, E.: Approximating minimum communication cost spanning trees and related problems. Master’s thesis, Weizmann Institute of Science, Rehovot, Israel (1999)
Scott, A.J.: The optimal network problem: Some computational procedures. Transportation Research 3(2), 201–210 (1969)
Wikipedia. Bridging (networking) (April 28, 2014), http://en.wikipedia.org/wiki/Bridging_(networ king)
Wong, R.T.: Worst-case analysis of network design problem heuristics. SIAM Journal of Algebraic Discrete Methods 1(1), 51–63 (1980)
Wu, B.Y., Chao, K.-M., Tang, C.Y.: Approximation algorithms for the shortest total path length spanning tree problem. Discrete Applied Mathematics 105(1), 273–289 (2000)
Wu, B.Y., Lancia, G., Bafna, V., Chao, K.-M., Ravi, R., Tang, C.Y.: A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM Journal on Computing 29(3), 761–778 (1999)
Wu, B.Y.: A polynomial time approximation scheme for the two-source minimum routing cost spanning trees. Journal of Algorithms 44(2), 359–378 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Hochuli, A., Holzer, S., Wattenhofer, R. (2014). Distributed Approximation of Minimum Routing Cost Trees. In: Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2014. Lecture Notes in Computer Science, vol 8576. Springer, Cham. https://doi.org/10.1007/978-3-319-09620-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-09620-9_11
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09619-3
Online ISBN: 978-3-319-09620-9
eBook Packages: Computer ScienceComputer Science (R0)