Approximation algorithms for longest-lived directional multicast communications in WANETs.
Song GuoOliver W. W. YangVictor C. M. LeungPublished in: MobiHoc (2007)
Keyphrases
- approximation algorithms
- np hard
- special case
- vertex cover
- worst case
- set cover
- routing algorithm
- wireless networks
- network design problem
- minimum cost
- approximation ratio
- np hardness
- approximation schemes
- precedence constraints
- constant factor
- undirected graph
- polynomial time approximation
- facility location problem
- primal dual
- communication networks
- linear programming
- linear program
- randomized algorithms
- theoretical analysis
- scheduling problem
- open shop
- disjoint paths