The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover.
Dana MoshkovitzPublished in: APPROX-RANDOM (2012)
Keyphrases
- np hardness
- set cover
- np hard
- approximation algorithms
- discrete tomography
- greedy heuristics
- special case
- upper bound
- worst case
- lower bound
- scheduling problem
- worst case analysis
- optimal solution
- greedy heuristic
- minimum cost
- integer programming
- knapsack problem
- greedy algorithm
- linear programming
- computational complexity
- decision problems
- linear program
- primal dual
- network flow
- genetic algorithm
- simulated annealing