Name
Title | ||
|---|---|---|
A sub-constant improvement in approximating the positive semidefinite Grothendieck problem. |
Abstract | ||
|---|---|---|
Semidefinite relaxations are a powerful tool for approximately solving combinatorial optimization problems such as MAX-CUT and the Grothendieck problem. By exploiting a bounded rank property of extreme points in the semidefinite cone, we make a sub-constant improvement in the approximation ratio of one such problem. Precisely, we describe a polynomial-time algorithm for the positive semidefinite Grothendieck problem -- based on rounding from the standard relaxation -- that achieves a ratio of $2/\pi + \Theta(1/{\sqrt n})$, whereas the previous best is $2/\pi + \Theta(1/n)$. We further show a corresponding integrality gap of $2/\pi+\tilde{O}(1/n^{1/3})$. |
Year | Venue | Field |
|---|---|---|
2014 | CoRR | Pi,Extreme point,Discrete mathematics,Combinatorics,Combinatorial optimization problem,Positive-definite matrix,Rounding,Tilde,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1408.2270 | 0 |
PageRank | References | Authors |
0.34 | 4 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Roy Frostig | 1 | 347 | 12.25 |
| Sida Wang | 2 | 541 | 44.65 |