# An average case analysis of the minimum spanning tree heuristic for the range assignment problem

Research output: Book/ReportReportProfessional

### Abstract

We present an average case analysis of the minimum spanning tree heuristic for the range assignment problem on a graph with power weighted edges. It is well-known that the worst-case approximation ratio of this heuristic is 2. Our analysis yields the following results: (1) In the one dimensional case ($d = 1$), where the weights of the edges are 1 with probability $p$ and 0 otherwise, the average-case approximation ratio is bounded from above by $2-p$. (2) When $d =1$ and the distance between neighboring vertices is drawn from a uniform $[0,1]$-distribution, the average approximation ratio is bounded from above by $2-2^{-\alpha}$ where $\alpha$ denotes the distance power radient. (3) In Euclidean 2-dimensional space, with distance power gradient $\alpha = 2$, the average performance ratio is bounded from above by $1 + \log 2$.
Original language Undefined Enschede University of Twente, Department of Applied Mathematics 21 Published - Oct 2007

### Publication series

Name Memorandum / Department of Applied Mathematics University of Twente, Department of Applied Mathematics LNCS4549/1857 1874-4850 1874-4850

• MSC-68W25
• IR-64423
• EWI-11259
• MSC-68W40
• METIS-242004

### Cite this

Boucherie, R. J., & de Graaf, M. (2007). An average case analysis of the minimum spanning tree heuristic for the range assignment problem. (Memorandum / Department of Applied Mathematics; No. LNCS4549/1857). Enschede: University of Twente, Department of Applied Mathematics.