### 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 | |

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 |

### Fingerprint

### Keywords

- Minimum spanning tree
- Power assignment
- Random graphs

### Cite this

}

**Average case analysis of the MST-heuristic for the power assignment problem : Special cases.** / de Graaf, Maurits; Boucherie, Richardus J.; Hurink, Johann L.; van Ommeren, Jan C.W.

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

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 -