Average case analysis of the MST-heuristic for the power assignment problem: Special cases

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
56 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 have the following results: (a) In the one-dimensional case, with uniform [0,1]-distributed distances, the expected approximation ratio is bounded above by 2-2=(p+2), where p 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.

Original languageEnglish
Article numbere5
JournalEAI Endorsed Transactions on Energy Web
Volume16
Issue number10
DOIs
Publication statusPublished - 4 Jan 2016
Event9th EAI International Conference on Performance Evaluation Methodologies and Tools 2015 - Berlin, Germany
Duration: 14 Dec 201516 Dec 2015
Conference number: 9
http://archive.valuetools.org/2015/show/home

Keywords

  • Minimum spanning tree
  • Power assignment
  • Random graphs

Fingerprint Dive into the research topics of 'Average case analysis of the MST-heuristic for the power assignment problem: Special cases'. Together they form a unique fingerprint.

  • Cite this