An average case analysis of the minimum spanning tree heuristic for the power assignment problem. Issue 1 (6th December 2018) - Graaf, Maurits; Boucherie, Richard J.; Hurink, Johann L.; van Ommeren, Jan‐Kees
Abstract : We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst‐case approximation ratio of this heuristic is 2. We show that in Euclidean d ‐dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0, 1] d, and the distance power gradient equals the dimension d, the minimum spanning tree‐based power assignment converges completely to a constant depending only on d .