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

Research output: Contribution to journalArticleAcademicpeer-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

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

}

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 -