|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Rounding Semidefinite Programming Hierarchies via Global Correlation | | Boaz Barak
; Prasad Raghavendra
; David Steurer
; | | Date: |
25 Apr 2011 | | Abstract: | We show a new way to round vector solutions of semidefinite programming (SDP)
hierarchies into integral solutions, based on a connection between these
hierarchies and the spectrum of the input graph. We demonstrate the utility of
our method by providing a new SDP-hierarchy based algorithm for constraint
satisfaction problems with 2-variable constraints (2-CSP’s).
More concretely, we show for every 2-CSP instance I a rounding algorithm for
r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution
that is at most eps worse than the relaxation’s value (normalized to lie in
[0,1]), as long as r > kcdot
ank_{geq heta}(Ins)/poly(e) ;, where k is
the alphabet size of I, $ heta=poly(e/k)$, and $
ank_{geq heta}(Ins)$
denotes the number of eigenvalues larger than $ heta$ in the normalized
adjacency matrix of the constraint graph of $Ins$.
In the case that $Ins$ is a uniquegames instance, the threshold $ heta$ is
only a polynomial in $e$, and is independent of the alphabet size. Also in
this case, we can give a non-trivial bound on the number of rounds for
emph{every} instance. In particular our result yields an SDP-hierarchy based
algorithm that matches the performance of the recent subexponential algorithm
of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a
natural family of instances, thus further restricting the set of possible hard
instances for Khot’s Unique Games Conjecture.
Our algorithm actually requires less than the $n^{O(r)}$ constraints
specified by the $r^{th}$ level of the Lasserre hierarchy, and in some cases
$r$ rounds of our program can be evaluated in time $2^{O(r)}poly(n)$. | | Source: | arXiv, 1104.4680 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER