Name
Abstract | ||
|---|---|---|
The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2488608.2488618 | Theory of Computing |
Keywords | DocType | Volume |
classical grothendieck inequality,grothendieck inequality,efficient rounding,np-hard optimization problem,algorithmic interpretation,constant-factor polynomial time approximation,noncommutative grothendieck inequality,cut norm problem,approximation algorithm,optimization problem,orthogonal procrustes problem,additional application,semidefinite programming | Journal | 10 |
Citations | PageRank | References |
4 | 0.41 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Assaf Naor | 1 | 750 | 64.06 |
| Oded Regev | 2 | 2322 | 133.33 |
| Thomas Vidick | 3 | 377 | 31.69 |