Local Approximation Algorithms for Scheduling Problems in Sensor Networks.
Patrik FloréenPetteri KaskiTopi MustoJukka SuomelaPublished in: ALGOSENSORS (2007)
Keyphrases
- sensor networks
- approximation algorithms
- scheduling problem
- np hard
- single machine
- wireless sensor networks
- precedence constraints
- special case
- sensor data
- processing times
- flowshop
- vertex cover
- data streams
- worst case
- sensor nodes
- energy efficient
- optimal solution
- environmental monitoring
- energy consumption
- tabu search
- set cover
- job shop scheduling
- lower bound
- resource constrained
- sensor readings
- approximation ratio
- job shop scheduling problem
- data aggregation
- communication cost
- branch and bound algorithm
- base station
- setup times
- mobile wireless
- mobile sensor networks
- data gathering
- communication bandwidth
- linear programming
- randomized algorithms
- strongly np hard
- underwater acoustic
- constant factor
- primal dual
- job shop
- sequence dependent setup times
- sensor web
- network connectivity
- computational complexity
- upper bound
- constraint satisfaction problems
- key establishment
- routing protocol
- visual sensor networks