Name
Abstract | ||
|---|---|---|
Goemans showed that any n points x_1,..., x_n in d-dimensions satisfying l_2^2 triangle inequalities can be embedded into l_{1}, with worst-case distortion at most sqrt{d}. We consider an extension of this theorem to the case when the points are approximately low-dimensional as opposed to exactly low-dimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an l_{2}^{2}-to-l_{1} embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns {x_i-x_j}_{iu003cj}. Average distortion embedding suffices for applications such as the SPARSEST CUT problem. Our embedding gives an approximation algorithm for the SPARSEST CUT problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, in Proc. 17th APPROX, 2014]. Our ideas give a new perspective on l_{2}^{2} metric, an alternate proof of Goemansu0027 theorem, and a simpler proof for average distortion sqrt{d}. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.4230/LIPIcs.FSTTCS.2016.10 | foundations of software technology and theoretical computer science |
Field | DocType | Volume |
Binary logarithm,Approximation algorithm,Average distortion,Discrete mathematics,Graph,Combinatorics,Embedding,Matrix (mathematics),Triangle inequality,Distortion,Mathematics | Conference | 65 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amit Deshpande | 1 | 676 | 40.91 |
| Prahladh Harsha | 2 | 371 | 32.06 |
| rakesh venkat | 3 | 3 | 2.77 |