On Approximation Algorithms for Interference-Aware Broadcast Scheduling in 2D and 3D Wireless Sensor Networks.
Ravi TiwariThang N. DinhMy T. ThaiPublished in: WASA (2009)
Keyphrases
- approximation algorithms
- broadcast scheduling
- wireless sensor networks
- np hard
- special case
- vertex cover
- sensor networks
- routing algorithm
- energy consumption
- worst case
- minimum cost
- multipath
- resource constrained
- network design problem
- sensor nodes
- primal dual
- open shop
- approximation schemes
- facility location problem
- set cover
- np hardness
- routing protocol
- approximation ratio
- base station
- randomized algorithms
- disjoint paths
- precedence constraints
- constant factor
- multi hop
- strongly np hard
- combinatorial auctions
- constant factor approximation
- lower bound