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

13 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 languageEnglish
Article numberRSA20831
Pages (from-to)89-103
Number of pages15
JournalRandom Structures and Algorithms
Volume55
Issue number1
Early online date6 Dec 2018
DOIs
Publication statusE-pub ahead of print/First online - 6 Dec 2018

Fingerprint

Average-case Analysis
Minimum Spanning Tree
Assignment Problem
Random variables
Heuristics
Identically distributed
Euclidean
Assignment
Random variable
Gradient
Converge
Approximation
Vertex of a graph

Keywords

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

Cite this

de Graaf, Maurits ; Boucherie, Richard ; Hurink, Johann L. ; van Ommeren, Jan C.W. / An average case analysis of the minimum spanning tree heuristic for the power assignment problem. In: Random Structures and Algorithms. 2018 ; Vol. 55, No. 1. pp. 89-103.
@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 = "2018",
month = "12",
day = "6",
doi = "10.1002/rsa.20831",
language = "English",
volume = "55",
pages = "89--103",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "Wiley",
number = "1",

}

de Graaf, M, Boucherie, R, Hurink, JL & van Ommeren, JCW 2018, 'An average case analysis of the minimum spanning tree heuristic for the power assignment problem', Random Structures and Algorithms, vol. 55, no. 1, RSA20831, pp. 89-103. https://doi.org/10.1002/rsa.20831

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.

In: Random Structures and Algorithms, Vol. 55, No. 1, RSA20831, 06.12.2018, p. 89-103.

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 -

de Graaf M, Boucherie R, Hurink JL, van Ommeren JCW. An average case analysis of the minimum spanning tree heuristic for the power assignment problem. Random Structures and Algorithms. 2018 Dec 6;55(1):89-103. RSA20831. https://doi.org/10.1002/rsa.20831

Access to Document

    Related content

    Research Output

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

    Research output: Book/Report › Report › Professional