Approximation algorithms for job scheduling with block-type conflict graphs.
Hanna FurmanczykTytus PikiesInka SokolowskaKrzysztof TurowskiPublished in: Comput. Oper. Res. (2024)
Keyphrases
- approximation algorithms
- job scheduling
- undirected graph
- np hard
- special case
- vertex cover
- worst case
- minimum cost
- approximation guarantees
- approximation ratio
- randomized algorithms
- primal dual
- constant factor
- load balancing
- precedence constraints
- polynomial time approximation
- identical machines
- resource allocation
- directed graph