@book{a8067aedfe0c44f487a47f6d83815e1a,

title = "An average case analysis of the minimum spanning tree heuristic for the range assignment problem",

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$.",

keywords = "MSC-68W25, IR-64423, EWI-11259, MSC-68W40, METIS-242004",

author = "Boucherie, {Richardus J.} and {de Graaf}, Maurits",

note = "http://eprints.ewi.utwente.nl/11259 ",

year = "2007",

month = oct,

language = "Undefined",

series = "Memorandum / Department of Applied Mathematics",

publisher = "University of Twente, Department of Applied Mathematics",

number = "LNCS4549/1857",

}