Finding minimum label spanning trees using cross‐entropy method. Issue 2 (26th May 2021)

• Record Type: Journal Article
• Authors: Vaisman, Radislav
• Is Part Of: Networks. Volume 79:Issue 2(2022)
• Page Start: 220
• Page End: 235
• Publication Date: 2021-05-26
• Subjects: communication network design -- cross‐Entropy -- data compression -- evolutionary optimization -- minimum label spanning tree; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22057
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: Obtaining high‐quality solutions to the minimum label spanning tree problem is of crucial importance to efficient communication network design, since such solutions can reduce both the construction cost and the complexity of the ultimate architecture. However, the corresponding optimization task was shown to be hard even for complete graphs. As a consequence, no computationally efficient method for solving this problem exactly in a reasonable time is known to exist and one has to rely on approximation techniques such as heuristic and evolutionary algorithms. In this study, we investigate the performance of a different method called the Cross‐Entropy algorithm which relies on rigorous developments in the fields of information theory and stochastic simulation. Our findings indicate that the mathematical soundness of the Cross‐Entropy method makes it very reliable and robust as compared to its counterparts. In particular, the obtained results suggest that the Cross‐Entropy method is not sensitive to different graph models and that the proposed algorithm can obtain optimal or near‐optimal solutions while using a reasonable computational effort.