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

Maurits  de Graaf; Richard Boucherie; Johann L. Hurink; Jan C.W. van Ommeren

doi:10.1002/rsa.20831

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

Maurits de Graaf (Corresponding Author), Richard Boucherie, Johann L. Hurink, Jan C.W. van Ommeren

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

1 Citation (Scopus)

30 Downloads (Pure)

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.

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	https://doi.org/10.1002/rsa.20831
Publication status	Published - Aug 2019

Keywords

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

Access to Document

10.1002/rsa.20831Licence: CC BY-NC-ND

Graaf2018averageFinal published version, 390 KBLicence: CC BY-NC-ND

Fingerprint Dive into the research topics of 'An average case analysis of the minimum spanning tree heuristic for the power assignment problem'. Together they form a unique fingerprint.

Cite this

@article{4a464fb9ef524e0b89b53c9985daf825,

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

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

author = "{de Graaf}, Maurits and Richard Boucherie and Hurink, {Johann L.} and {van Ommeren}, {Jan C.W.}",

note = "Wiley deal This research was supported by the Nederlands Organisation for Scientific Research (N.W.O.).",

year = "2019",

month = aug,

doi = "10.1002/rsa.20831",

language = "English",

volume = "55",

pages = "89--103",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "1",

}

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 - 2019/8

Y1 - 2019/8

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 -