English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present an approximation scheme for optimizing certain Quadratic IntegerProgramming problems with positive semidefinite objective functions and globallinear constraints. This framework includes well known graph problems such asMinimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Setexpansion, as well as the Unique Games problem. These problems are notoriousfor the existence of huge gaps between the known algorithmic results andNP-hardness results. Our algorithm is based on rounding semidefinite programsfrom the Lasserre hierarchy, and the analysis uses bounds for low-rankapproximations 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$'thsmallest eigenvalue of the normalized graph Laplacian $\mathcal{L}$. In thecase of graph bisection and small set expansion, the number of vertices in thecut 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 $\mathcal{L}$ smaller than$1-\epsilon$.  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 UniqueGames on expanders, and also shows that Lasserre SDPs are powerful enough tosolve well-known integrality gap instances for the basic SDP.  We also give an algorithm for independent sets in graphs that performs wellwhen the Laplacian does not have too many eigenvalues bigger than $1+o(1)$.

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives