On the Hardness of Scheduling With Non-Uniform Communication Delays.
Sami DaviesJanardhan KulkarniThomas RothvossSai SandeepJakub TarnawskiYihao ZhangPublished in: SODA (2022)
Keyphrases
- communication delays
- np hard
- control theory
- precedence relations
- execution times
- directed networks
- multiprocessor systems
- scheduling problem
- processing times
- computational complexity
- np complete
- lower bound
- special case
- worst case
- precedence constraints
- approximation algorithms
- lagrangian relaxation
- objective function
- search algorithm