A communication assignment problem on trees: Heuristics and asymptotic behavior

In the communication assignment problem on trees (CAP-T) a system of communication centers C-1, C-2, ..., C-n has to be embedded into a given tree G on n nodes. The centers exchange messages at given rates per time unit. If there is no direct connection between centers C-i and C-j, the messages sent from C-i to C-j are routed through several intermediate centers. The goal is to find an embedding of the centers into the nodes of G which minimizes the maximum intermediate traffic over all centers. It has been shown that this problem is NP-hard even if the given tree G is a star of branch length three [3]. In the first part of this paper we test and compare simulated annealing and tabu search approaches for the CAP-T. The numerical experiments involve random test instances of size between 7 and 100. Both algorithms use a new neighborhood structure in the set of permutations which exploits the combinatorial structure of the problem at hand. The second part of the paper investigates the asymptotic behavior of the CAP-T. It is shown that, under natural probabilistic constraints on the problem data, the ratio between the maximum and the minimum values of the objective function taken over the whole set of feasible solutions approaches 1 with probability tending to 1, as the size of the problem tends to infinity. In other words, each feasible solution approaches the optimal one as the size of the problem tends to infinity, that is the CAP-T tends to become in a certain sense trivial as its size increases.