Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover.
Sushant SachdevaRishi SaketPublished in: Computational Complexity Conference (2013)
Keyphrases
- vertex cover
- approximation algorithms
- np hard
- scheduling problem
- worst case
- minimum cost
- optimal solution
- precedence constraints
- constant factor
- special case
- optimality criterion
- np complete
- single machine
- flowshop
- approximation guarantees
- greedy heuristic
- polynomial time approximation
- computational complexity
- lower bound
- higher order
- dynamic programming
- finding optimal
- branch and bound algorithm
- parallel machines
- tabu search
- constraint satisfaction problems