Approximation Algorithms for Scheduling with Class Constraints.
Klaus JansenAlexandra LassotaMarten MaackPublished in: SPAA (2020)
Keyphrases
- approximation algorithms
- precedence constraints
- np hard
- special case
- worst case
- vertex cover
- scheduling problem
- minimum cost
- resource constraints
- constant factor
- set cover
- network design problem
- primal dual
- randomized algorithms
- facility location problem
- approximation schemes
- np hardness
- approximation ratio
- resource allocation
- network flow
- global constraints
- setup times
- traveling salesman problem
- sequence dependent setup times
- approximation guarantees
- polynomial time approximation
- disjoint paths