Hardness and Approximation of the Survivable Multi-Level Fat Tree Problem
Hung Q. Ngo, Thị Nguyệt Nguyễn, D. Xu · 2009
With the explosive deployment of "triple play" (voice, video and data services) over the same access network, guaranteeing a certain-level of survivability for the access network is becoming critical for service providers. The problem of economically provisioning survivable access networks has given rise to a new class of network design problems, including the so-called survivable multi-level fat tree problem (SMFT). We show that two special cases of SMFT are polynomial- time solvable, and present two approximation algorithms for the general case. The first is a combinatorial algorithm with approximation ratio min{[~L/2] + 1, 2log2n} where L is the longest Steiner path length between two terminals, and n is the number of nodes. The second is a primal-dual (2Deltas+ 2)- approximation algorithm where Deltasis the maximum Sterner degree of terminals in the access network. We then show that approximating SMFT to within a certain constant c > 1 is NP- hard, even when all edge-weights of G are 1, L les 10, and Deltasles 3. Finally, we experimentally show that the approximation algorithms perform extremely well on random instances of the problem.