Randomized rounding
Kent Quanrud · 75:34
This lecture shows how to turn NP-hard discrete problems into approximation algorithms by writing an integer program, relaxing it to a polynomial-time solvable LP, then interpreting the fractional solution as independ...