### Abstract

Original language | English |
---|---|

Article number | RSA20831 |

Pages (from-to) | 89-103 |

Number of pages | 15 |

Journal | Random Structures and Algorithms |

Volume | 55 |

Issue number | 1 |

Early online date | 6 Dec 2018 |

DOIs | |

Publication status | E-pub ahead of print/First online - 6 Dec 2018 |

### Fingerprint

### Keywords

- UT-Hybrid-D
- Analysis of algorithms
- Approximation algorithms
- Average case analysis
- Point processes
- Power assignment
- Range assignment
- Ad-hoc networks

### Cite this

}

**An average case analysis of the minimum spanning tree heuristic for the power assignment problem.** / de Graaf, Maurits (Corresponding Author); Boucherie, Richard; Hurink, Johann L.; van Ommeren, Jan C.W.

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

TY - JOUR

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

AU - de Graaf, Maurits

AU - Boucherie, Richard

AU - Hurink, Johann L.

AU - van Ommeren, Jan C.W.

N1 - Wiley deal This research was supported by the Nederlands Organisation for Scientific Research (N.W.O.).

PY - 2018/12/6

Y1 - 2018/12/6

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

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

KW - UT-Hybrid-D

KW - Analysis of algorithms

KW - Approximation algorithms

KW - Average case analysis

KW - Point processes

KW - Power assignment

KW - Range assignment

KW - Ad-hoc networks

U2 - 10.1002/rsa.20831

DO - 10.1002/rsa.20831

M3 - Article

VL - 55

SP - 89

EP - 103

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 1

M1 - RSA20831

ER -