Approximation Algorithms for Channel Allocation Problems in Broadcast Networks.
Rajiv GandhiSamir KhullerAravind SrinivasanNan WangPublished in: RANDOM-APPROX (2003)
Keyphrases
- approximation algorithms
- allocation problems
- np hard
- special case
- resource allocation
- vertex cover
- cellular networks
- worst case
- facility location problem
- minimum cost
- set cover
- np hardness
- randomized algorithms
- network design problem
- constant factor approximation
- disjoint paths
- open shop
- network structure
- approximation schemes
- undirected graph
- combinatorial auctions
- complex networks
- approximation ratio
- network design
- precedence constraints
- lower bound
- assembly line
- primal dual
- wireless networks