Abstract:
We consider the following NP-hard generalization of the Minimum Spanning Tree problem. Given an undirected $n$-vertex edge-weighted complete graph and integers $d$ and $m$, find $m$ edge-disjoint spanning trees of diameter at most $d$ with minimum total weight. We propose a new polynomial-time approximation algorithm for the problem and study its performance guarantees on random inputs, that is, when the edge weights of the graph are i. i. d. random variables. We show that under mild conditions on the distribution parameters the proposed algorithm is asymptotically optimal for the case of continuous and discrete uniform distribution on $[a_n, b_n]$, $a_n>0$, the shifted exponential distribution with shift $a_n>0$, and distributions dominating the above. In contrast to a number of previous results for related problems, the new algorithm is asymptotically optimal not only if $d$ tends to infinity with $n$, but for constant $d$ as well.
Fulltext:
PDF file (271 kB)