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

Research output: Book/ReportReportProfessional

191 Downloads (Pure)

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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages21
Publication statusPublished - Oct 2007

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherUniversity of Twente, Department of Applied Mathematics
No.LNCS4549/1857
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

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

Cite this