Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints.
Stefano LeonardiAlberto Marchetti-SpaccamelaAndrea VitalettiPublished in: FSTTCS (2000)
Keyphrases
- approximation algorithms
- real time
- allocation problems
- np hard
- special case
- worst case
- precedence constraints
- vertex cover
- resource allocation
- disjoint paths
- constant factor
- primal dual
- minimum cost
- facility location problem
- approximation schemes
- randomized algorithms
- approximation ratio
- set cover
- central processing unit
- network design problem
- constraint programming
- open shop
- constant factor approximation
- np hardness
- polynomial time approximation
- lower bound
- approximation guarantees
- global constraints
- multistage
- dynamic programming