Approximation algorithms for computing minimum exposure paths in a sensor field.
Hristo N. DjidjevPublished in: ACM Trans. Sens. Networks (2010)
Keyphrases
- approximation algorithms
- minimum cost
- constant factor
- disjoint paths
- np hard
- vertex cover
- special case
- worst case
- network design problem
- set cover
- randomized algorithms
- np hardness
- primal dual
- exact algorithms
- open shop
- facility location problem
- precedence constraints
- approximation schemes
- approximation ratio
- combinatorial auctions
- sensor networks
- undirected graph
- spanning tree
- branch and bound
- linear programming
- constant factor approximation