Name
Title | ||
|---|---|---|
An average case analysis of the minimum spanning tree heuristic for the power assignment problem. |
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 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1002/rsa.20831 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | DocType | Volume |
ad-hoc networks,analysis of algorithms,approximation algorithms,average case analysis,point processes,power assignment,range assignment | Journal | 55.0 |
Issue | ISSN | Citations |
1.0 | 1042-9832 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maurits De Graaf | 1 | 30 | 9.05 |
| Richard J. Boucherie | 2 | 311 | 37.73 |
| Johann L. Hurink | 3 | 154 | 21.00 |
| Jan-kees C. W. Van Ommeren | 4 | 73 | 8.53 |