An average case analysis of the minimum spanning tree heuristic for the power assignment problem

Maurits de Graaf (Corresponding Author), Richard Boucherie, Johann L. Hurink, Jan C.W. van Ommeren

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
124 Downloads (Pure)

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.
Original languageEnglish
Article numberRSA20831
Pages (from-to)89-103
Number of pages15
JournalRandom Structures and Algorithms
Volume55
Issue number1
Early online date6 Dec 2018
DOIs
Publication statusPublished - Aug 2019

Keywords

  • UT-Hybrid-D
  • Analysis of algorithms
  • Approximation algorithms
  • Average case analysis
  • Point processes
  • Power assignment
  • Range assignment
  • Ad-hoc networks

Fingerprint

Dive into the research topics of 'An average case analysis of the minimum spanning tree heuristic for the power assignment problem'. Together they form a unique fingerprint.

Cite this