ew 16(10): e5

Research Article

Average Case Analysis of the MST-heuristic for the Power Assignment Problem: Special Cases

Download349 downloads
Cite
BibTeX Plain Text
  • @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
Maurits de Graaf1,*, Richard Boucherie2, Johann Hurink2, Jan-Kees van Ommeren2
  • 1: Thales Nederland B.V., University of Twente
  • 2: University of Twente
*Contact email: M.deGraaf@utwente.nl

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 [0, 1]-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ζ(3), where ζ denotes the Riemann zeta function.

Keywords
power assignment, minimum spanning tree, random graphs
Published
4th Jan 2016
Publisher
ACM
http://dx.doi.org/10.4108/eai.14-12-2015.2262699

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.