Abstract
Convex relaxations based on different hierarchies of linear/semi–definite programs have been used recently to devise approximation algorithms for various optimization problems. The approximation guarantee of these algorithms improves with the number of rounds r in the hierarchy, though the complexity of solving (or even writing down the solution for) the r'th level program grows as $n^{\Omega(r)}$ where n is the input size.
In this work, we observe that many of these algorithms are based on local rounding procedures that only use a small part of the SDP solution (of size $n^{O(1)}2^{O(r)}$ instead of $n^{\Omega(r)}$). We give an algorithm to find the requisite portion in time polynomial in its size. The challenge in achieving this is that the required portion of the solution is not fixed a priori but depends on other parts of the solution, sometimes in a complicated iterative manner. Our solver leads to $poly(n) 2^{O(r)}$ time algorithms to obtain the same guarantees in many cases as the earlier $n^{O(r)}$ time algorithms based on r rounds of the Lasserre/SOS hierarchy. In particular, guarantees based on $O(\log n)$ rounds can be realized in polynomial time.
Joint work with Venkatesan Guruswami.