An average case analysis of the minimum spanning tree heuristic for the power assignment problem. Issue 1 (6th December 2018)

• Record Type: Journal Article
• Authors: Graaf, Maurits; Boucherie, Richard J.; Hurink, Johann L.; van Ommeren, Jan‐Kees
• Is Part Of: Random structures & algorithms. Volume 55:Issue 1(2019)
• Page Start: 89
• Page End: 103
• Publication Date: 2018-12-06
• Subjects: ad‐hoc networks -- analysis of algorithms -- approximation algorithms -- average case analysis -- point processes -- power assignment -- range assignment; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20831
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .