Approximation Algorithms for a Link Scheduling Problem in Wireless Relay Networks with QoS Guarantee.
Chi-Yao HongAi-Chun PangPi-Cheng HsiuPublished in: IEEE Trans. Mob. Comput. (2010)
Keyphrases
- approximation algorithms
- np hard
- scheduling problem
- precedence constraints
- quality of service
- strongly np hard
- end to end qos
- vertex cover
- special case
- minimum cost
- worst case
- approximation guarantees
- single machine
- lower bound
- traffic engineering
- flowshop
- approximation ratio
- processing times
- primal dual
- network resources
- constant factor
- linear programming
- undirected graph
- disjoint paths
- randomized algorithms
- setup times
- tabu search
- integer programming
- approximation schemes
- job shop scheduling
- multimedia services
- open shop
- parallel machines
- differentiated services
- sequence dependent setup times
- set cover
- optimal solution
- linear program
- lagrangian relaxation
- constant factor approximation
- polynomial time approximation
- multicast tree
- knapsack problem
- network structure
- computational complexity