ECCC-Report TR11-066https://eccc.weizmann.ac.il/report/2011/066Comments and Revisions published for TR11-066en-usThu, 19 May 2011 15:22:14 +0300
Revision 1
| Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives |
Venkatesan Guruswami,
Ali Kemal Sinop
https://eccc.weizmann.ac.il/report/2011/066#revision1We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix.
For all the above graph problems, we give an algorithm running in time $n^{O(r/\epsilon^2)}$ with approximation ratio $\frac{1+\epsilon}{\min\{1,\lambda_r\}}$, where $\lambda_r$ is the $r$'th smallest eigenvalue of the normalized graph Laplacian. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Similar bounds can be shown for $k$-way partitioning problems. Our results imply $(1+O(\epsilon))$ factor approximation in time $n^{O(r^\ast/\epsilon^2)}$ where $r^\ast$ is the number of eigenvalues of the normalized Laplacian smaller than $1-\epsilon$. This perhaps gives some indication as to why even showing mere APX-hardness for these problems has been elusive, since the reduction must produce graphs with a slowly growing spectrum (and classes like planar graphs which are known to have such a spectral property often admit good algorithms owing to their nice structure).
For Unique Games, we give a factor $(1+\frac{2+\epsilon}{\lambda_r})$ approximation for minimizing the number of unsatisfied constraints in $n^{O(r/\epsilon)}$ time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve well-known integrality gap instances for the basic SDP.
We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than $1+o(1)$.
Thu, 19 May 2011 15:22:14 +0300https://eccc.weizmann.ac.il/report/2011/066#revision1
Paper TR11-066
| Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives |
Venkatesan Guruswami,
Ali Kemal Sinop
https://eccc.weizmann.ac.il/report/2011/066We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix.
For all the above graph problems, we give an algorithm running in time $n^{O(r/\epsilon^2)}$ with approximation ratio $\frac{1+\epsilon}{\min\{1,\lambda_r\}}$, where $\lambda_r$ is the $r$'th smallest eigenvalue of the normalized graph Laplacian. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply $(1+O(\epsilon))$ factor approximation in time $n^{O(r^\ast/\epsilon^2)}$ where $r^\ast$ is the number of eigenvalues of the normalized Laplacian smaller than $1-\epsilon$. This perhaps gives some indication as to why even showing mere APX-hardness for these problems has been elusive, since the reduction must produce graphs with a slowly growing spectrum (and classes like planar graphs which are known to have such a spectral property often admit good algorithms owing to their nice structure).
For Unique Games, we give a factor $(1+\frac{2+\epsilon}{\lambda_r})$ approximation for minimizing the number of unsatisfied constraints in $n^{O(r/\epsilon)}$ time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve well-known integrality gap instances for the basic SDP.
We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than $1+o(1)$.
Mon, 25 Apr 2011 15:29:45 +0300https://eccc.weizmann.ac.il/report/2011/066