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

Maurits de Graaf; Richardus J. Boucherie; Johann L. Hurink; Jan C.W. van Ommeren

doi:10.4108/eai.14-12-2015.2262699

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

Maurits de Graaf, Richardus J. Boucherie, Johann L. Hurink, Jan C.W. van Ommeren

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

112 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 language	English
Article number	e5
Journal	EAI Endorsed Transactions on Energy Web
Volume	16
Issue number	10
DOIs	https://doi.org/10.4108/eai.14-12-2015.2262699
Publication status	Published - 4 Jan 2016
Event	9th EAI International Conference on Performance Evaluation Methodologies and Tools 2015 - Berlin, Germany Duration: 14 Dec 2015 → 16 Dec 2015 Conference number: 9 http://archive.valuetools.org/2015/show/home

Keywords

Minimum spanning tree
Power assignment
Random graphs

Access to Document

10.4108/eai.14-12-2015.2262699

eai.14-12-2015.2262699Final published version, 243 KB

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 = jan,

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",

note = "9th EAI International Conference on Performance Evaluation Methodologies and Tools 2015, VALUETOOLS 2015 ; Conference date: 14-12-2015 Through 16-12-2015",

url = "http://archive.valuetools.org/2015/show/home",

}

TY - JOUR

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

T2 - 9th EAI International Conference on Performance Evaluation Methodologies and Tools 2015

AU - de Graaf, Maurits

AU - Boucherie, Richardus J.

AU - Hurink, Johann L.

AU - van Ommeren, Jan C.W.

N1 - Conference code: 9

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

SN - 2032-944X

VL - 16

JO - EAI Endorsed Transactions on Energy Web

JF - EAI Endorsed Transactions on Energy Web

IS - 10

M1 - e5

Y2 - 14 December 2015 through 16 December 2015

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this