Average Case Analysis of the MST-heuristic for the Power Assignment Problem: Special Cases
2016
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-dimension\-al case, with uniform $\left[ 0,1 \right]$-distributed distances, the expected approximation ratio is bounded above by $2 - 2/(\myp+2)$, where $\myp$ 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\zeta(3)$, where $\zeta$ denotes the Riemann zeta function.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
1
Citations
NaN
KQI