LP and SDP rounding techniques
4 methods in the atlas attack this one problem. They are rivals: each wins something the others do not.
Phrasings that mean this problem
Approximation via LPInteger program approximationAssignment approximationFractional packing-covering
approximation
- Multiplicative weights LPPlotkin-Shmoys-Tardosspecialistapproximation
- Iterative LP roundingBasic feasible extreme pointsspecialistapproximation
- Randomized roundingChernoff concentrationstandardapproximation
- Dependent roundingstandalonespecialistapproximation