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

Research output: Contribution to journalArticleAcademicpeer-review

29 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 statusE-pub ahead of print/First online - 6 Dec 2018

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