About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
9th EAI International Conference on Performance Evaluation Methodologies and Tools

Research Article

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

Cite
BibTeX Plain Text
  • @INPROCEEDINGS{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},
        proceedings={9th EAI International Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        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
    VALUETOOLS
    ICST
    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 $\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.

Keywords
power assignment minimum spanning tree random graphs
Published
2016-01-04
Publisher
ACM
http://dx.doi.org/10.4108/eai.14-12-2015.2262699
Copyright © 2015–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL