Randomized rounding
Kent Quanrud · 96:54
This lecture introduces randomized rounding: model an NP-hard discrete problem as an integer program, relax it to a polynomial-time linear program, then interpret fractional values as probabilities to recover a discre...