Randomized rounding (Fundamental algorithms, Spring 2023, Lecture 22)
Kent Quanrud · 73:01
This lecture shows how to approximate NP-hard discrete problems by relaxing an integer program to a polynomial-time linear program and converting the fractional solution into a discrete one by randomized rounding. The...