Tight Hardness Results for Maximum Weight Rectangles.
Arturs BackursNishanth DikkalaChristos TzamosPublished in: ICALP (2016)
Keyphrases
- maximum weight
- np hard
- worst case
- lower bound
- bipartite graph
- bipartite matching
- minimum weight
- independent set
- partial order
- weighted graph
- upper bound
- bipartite graph matching
- computational complexity
- optimal solution
- approximation algorithms
- scheduling problem
- greedy heuristic
- special case
- multiscale
- low complexity
- multi class
- minimum cost