Randomized metarounding (extended abstract)
Robert D. Carr, Santosh Vempala · 2000
Let P be a linear relaxation of an integer polytope Z such that the integrality gap of P with respect to Z is at most r, as verified by a poly-time heuristic A, which on any positive cost function e returns an integer solution (extreme point of Z) whose cost is at most r times the optimal cost over P. Then for any point z" in P (fractional solution), rx" dominates some convex combination of extreme points of Z.A constructive version of this theorem is presented with applications to approximation algorithm% and can be viewed as a generalization of randomized rounding.