2a50e9c2d6b89b95bcb416d6857f8b45-Reviews.html

The authors propose an efficient scheme to solve LP relaxations of combinatorial optimization problems. Their contribution is a novel scheme and analysis that takes into account the original goal of constructing an integral feasible solution from the relaxed solution. They prove that an approximate solution is sufficient to construct an integral alpha-approximate solution to the vertex cover problem. They also prove a convergence result for an algorithm solving a suitably constructed QP approximation to a general standard form LP problem. The proposed method is evaluated experimentally on a number of combinatorial optimization problems and shown to be competitive with Cplex, a state-of-the-art LP solver.