Tight Hardness Results for Maximum Weight Rectangles.

Arturs Backurs Nishanth Dikkala Christos Tzamos

Published in: CoRR (2016)

Keyphrases

maximum weight
np hard
worst case
lower bound
bipartite graph
bipartite matching
minimum weight
partial order
upper bound
independent set
computational complexity
weighted graph
bipartite graph matching
approximation algorithms
low complexity
knapsack problem