A PTAS for the Metric Case of the Minimum Sum-Requirement Communication Spanning Tree Problem

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8959
• 期：1
• 页码：9-20
• 全文大小：256 KB
• 参考文献：1. Hu, T.C.: Optimum communication spanning trees. SIAM J. Comput.?3(3), 188-95 (1974) CrossRef
  2. Wu, B.Y., Chao, K.M.: Spanning Trees and Optimization Problems. Chapman & Hall / CRC (2004) ISBN: 1584884363
  3. Johnson, D.S., Lenstra, J.K., Rinnooy Kan, A.H.G.: The complexity of the network design problem. Networks?8, 279-85 (1978) CrossRef
  4. 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 J. on Computing?29(3), 761-78 (2000) CrossRef
  5. Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pp. 184-963 (1996)
  6. Talwar, K., Fakcharoenphol, J., Rao, S.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 448-55 (2003)
  7. Wu, B.Y., Chao, K.M., Tang, C.Y.: Approximation algorithms for some optimum communication spanning tree problems. Discrete and Applied Mathematics?102, 245-66 (2000) CrossRef
  8. Wu, B.Y., Chao, K.M., Tang, C.Y.: A polynomial time approximation scheme for optimal product-requirement communication spanning trees. J. Algorithms?36, 182-04 (2000) CrossRef
  9. Farley, A.M., Fragopoulou, P., Krumme, D., Proskurowski, A., Richards, D.: Multi-source spanning tree problems. Journal of Interconnection Networks?1(1), 61-1 (2000) CrossRef
  10. Wu, B.Y.: A polynomial time approximation scheme for the two-source minimum routing cost spanning trees. J. Algorithms?44, 359-78 (2002) CrossRef
  11. Orlin, B.J.: A faster strongly polynomial minimum cost flow algorithm. Operations Research?41(2), 338-50 (1993) CrossRef
  
• 作者单位：Santiago V. Ravelo (17)
  Carlos E. Ferreira (17)
  
  17. Instituto de Matemática e Estatística, Universidade de S?o Paulo, Brasil
  
• 丛书名：Algorithms and Discrete Applied Mathematics
• ISBN：978-3-319-14974-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

This work considers the metric case of the minimum sum-requirement communication spanning tree problem (SROCT), which is an NP-hard particular case of the minimum communication spanning tree problem (OCT). Given an undirected graph G--V,E) with non-negative lengths ω(e) associated to the edges satisfying the triangular inequality and non-negative routing weights r(u) associated to nodes u?∈-em class="a-plus-plus">V, the objective is to find a spanning tree T of G, that minimizes: \(\frac{1}{2}\sum_{u\in V}\sum_{v\in V}\left(r(u)+r(v)\right)d(T,u,v)\) , where d(H,x,y) is the minimum distance between nodes x and y in a graph H??-em class="a-plus-plus">G. We present a polynomial approximation scheme for the metric case of the SROCT improving the until now best existing approximation algorithm for this problem.