Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover.
Felix HappachAndreas S. SchulzPublished in: CoRR (2020)
Keyphrases
- approximation algorithms
- set cover
- np hard
- scheduling problem
- min sum
- linear programming
- special case
- worst case
- greedy algorithm
- minimum cost
- optimal solution
- lp relaxation
- network flow
- integer programming
- np complete
- greedy heuristic
- primal dual
- branch and bound algorithm
- lower bound
- message passing
- solution space
- undirected graph
- computational complexity
- linear program
- constraint satisfaction problems
- lagrangian relaxation
- min cut
- higher order
- denoising
- pairwise