TR12-111 Authors: Venkatesan Guruswami, Ali Kemal Sinop

Publication: 5th September 2012 15:18

Downloads: 939

Keywords:

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 {\em 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

{\em 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 $n^{O(1)} 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 hierarchy. In

particular, guarantees based on $O(\log n)$ rounds can be realized in

polynomial time. For instance, one can (i) get $O(1/\lambda_r)$

approximations for graph partitioning problems such as minimum

bisection and small set expansion in $n^{O(1)}

2^{O(r)}$ time, where $\lambda_r$ is the $r$'th smallest eigenvalue of

the graph's normalized Laplacian; (ii) a similar guarantee in

$n^{O(1)} k^{O(r)}$ for Unique Games where $k$ is the number of labels (the polynomial dependence on $k$ is new); and (iii) find an independent set of size $\Omega(n)$ in $3$-colorable graphs in $(n 2^r)^{O(1)}$ time provided $\lambda_{n-r} \le 1.11$.

We develop and describe our algorithm in a fairly general abstract

framework. The main technical tool in our work, which might be of

independent interest in convex optimization, is an efficient ellipsoid

algorithm based separation oracle for convex programs that can output

a {\em certificate of infeasibility with restricted support}. This is

used in a recursive manner to find a sequence of consistent points in

nested convex bodies that ``fools'' local rounding algorithms.