R. Jothi and B. Raghavachari (USA)
--Capacitated Minimum Spanning Trees, EsauWilliams Algorithm, Network Design, Heuristics.
--Given a set of terminals, each associated with a positive number denoting the traffic to be routed to a central terminal (root), the capacitated minimum spanning tree (CMST) problem asks for a minimum spanning tree, spanning all terminals, such that the amount of traffic routed from a subtree, linked to the root by an edge, does not exceed the given capacity constraint . The CMST problem is NP-complete and has been extensively studied for the past 40 years. Exact algorithms for solving the CMST problem are not useful, as their running times are exponential, and thus the size of the problem instances that they can solve to optimality, in reasonable amount of time, is still far from the size of the real-life instances. Numerous heuristics have been proposed to overcome the exponential time complexity of exact algorithms. The current best heuristic procedures are due to Amberg et al. [1], Sharaiha et al. [2], and Ahuja et al. [3]. A major problem with these heuristics is that their worst-case running-times are pseudo-polynomial, i.e., they could be exponential. The most popular and efficient heuristic for the CMST problem is due to Esau and Williams (EW), presented in 1966, with running time ǴҾ ҵ. Almost all of the heuristics that has been proposed so far, use EW algorithm as a benchmark to compare their results. Any other heuristic that outperforms EW algorithm do so with an enormous increase in running time. In this paper, we present the first ǴҾ ҵ algorithm in 37 years that comprehen sively outperforms the EW algorithm. Experimental results on benchmark instances show that our algorithm obtains improvements of upto 17% when compared to EW algorithm.
Important Links:
Go Back
