Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks.
Jing (Selena) HeShouling JiYi PanZhipeng CaiPublished in: Theor. Comput. Sci. (2013)
Keyphrases
- approximation algorithms
- wireless sensor networks
- np hard
- special case
- vertex cover
- worst case
- sensor networks
- minimum cost
- randomized algorithms
- facility location problem
- approximation ratio
- routing algorithm
- undirected graph
- exact algorithms
- primal dual
- energy consumption
- sensor nodes
- open shop
- lower bound
- resource constrained
- set cover
- constant factor
- approximation schemes
- energy efficiency
- precedence constraints
- upper bound
- dynamic programming
- constant factor approximation