# 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 English Enschede University of Twente, Department of Applied Mathematics 21 Published - Oct 2007

### Publication series

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

• MSC-68W25
• MSC-68W40

## Fingerprint

Dive into the research topics of 'An average case analysis of the minimum spanning tree heuristic for the range assignment problem'. Together they form a unique fingerprint.