Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover.
Felix HappachAndreas S. SchulzPublished in: Math. Oper. Res. (2024)
Keyphrases
- set cover
- approximation algorithms
- greedy heuristics
- np hard
- scheduling problem
- min sum
- special case
- linear programming relaxation
- worst case
- minimum cost
- greedy algorithm
- lower bound
- network flow
- integer programming
- knapsack problem
- linear programming
- primal dual
- greedy heuristic
- np complete
- branch and bound algorithm
- cutting plane
- computational complexity
- solution space
- feasible solution
- convex hull
- optimal solution
- mixed integer programming
- valid inequalities
- multistage