Research Article
Average Case Analysis of the MST-heuristic for the Power Assignment Problem: Special Cases
@ARTICLE{10.4108/eai.14-12-2015.2262699, author={Maurits de Graaf and Richard Boucherie and Johann Hurink and Jan-Kees van Ommeren}, title={Average Case Analysis of the MST-heuristic for the Power Assignment Problem: Special Cases}, journal={EAI Endorsed Transactions on Energy Web}, volume={3}, number={10}, publisher={ACM}, journal_a={EW}, year={2016}, month={1}, keywords={power assignment, minimum spanning tree, random graphs}, doi={10.4108/eai.14-12-2015.2262699} }- Maurits de Graaf
Richard Boucherie
Johann Hurink
Jan-Kees van Ommeren
Year: 2016
Average Case Analysis of the MST-heuristic for the Power Assignment Problem: Special Cases
EW
EAI
DOI: 10.4108/eai.14-12-2015.2262699
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 have the following results: (a) In the one-dimension-al case, with uniform $\left[ 0,1 \right]$-distributed distances, the expected approximation ratio is bounded above by $2 - 2/(\myp+2)$, where $\myp$ denotes the distance power gradient. (b) For the complete graph, with uniform $[0,1]$ distributed edge weights, the expected approximation ratio is bounded above by $2-1/2\zeta(3)$, where $\zeta$ denotes the Riemann zeta function.
Copyright © 2015 M. de Graaf et al., licensed to EAI. This is an open access article distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/3.0/), which permits unlimited use, distribution and reproduction in any medium so long as the original work is properly cited.
