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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
44 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

Fingerprint

Assignment problem
Approximation
Minimum spanning tree
Heuristics
Case analysis
Power distance
Gradient
Graph

Keywords

  • Minimum spanning tree
  • Power assignment
  • Random graphs

Cite this

@article{aa7666e8a148412ab0a2b6c67fc20b51,
title = "Average case analysis of the MST-heuristic for the power assignment problem: Special cases",
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.",
keywords = "Minimum spanning tree, Power assignment, Random graphs",
author = "{de Graaf}, Maurits and Boucherie, {Richardus J.} and Hurink, {Johann L.} and {van Ommeren}, {Jan C.W.}",
year = "2016",
month = "1",
day = "4",
doi = "10.4108/eai.14-12-2015.2262699",
language = "English",
volume = "16",
journal = "EAI Endorsed Transactions on Energy Web",
issn = "2032-944X",
publisher = "European Alliance for Innovation",
number = "10",

}

TY - JOUR

T1 - Average case analysis of the MST-heuristic for the power assignment problem

T2 - Special cases

AU - de Graaf, Maurits

AU - Boucherie, Richardus J.

AU - Hurink, Johann L.

AU - van Ommeren, Jan C.W.

PY - 2016/1/4

Y1 - 2016/1/4

N2 - 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.

AB - 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.

KW - Minimum spanning tree

KW - Power assignment

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=85010426619&partnerID=8YFLogxK

U2 - 10.4108/eai.14-12-2015.2262699

DO - 10.4108/eai.14-12-2015.2262699

M3 - Article

AN - SCOPUS:85010426619

VL - 16

JO - EAI Endorsed Transactions on Energy Web

JF - EAI Endorsed Transactions on Energy Web

SN - 2032-944X

IS - 10

M1 - e5

ER -