2017/06/21 by Yuval Rabani, Rabani, Yuval, Rakesh Venkat +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1706.06806
arxiv created 2017/06/21 · arxiv updated 2017/06/22
We consider the problem of embedding a finite set of points \x1, …, xn\ ∈ ℝd that satisfy ℓ22 triangle inequalities into ℓ1, when the points are approximately low-dimensional. Goemans (unpublished, appears in a work of [Magen and Moharammi, 2008]) showed that such points residing in exactly d dimensions can be embedded into ℓ1 with distortion at most √(d). We prove the following robust analogue of this statement: if there exists a r-dimensional subspace Π such that the projections onto this subspace satisfy ∑i,j ∈ [n]\Vert Πxi - Πxj \Vert 22 ≥ Ω(1) ∑i,j ∈ [n]\Vert xi - xj \Vert 22, then there is an embedding of the points into ℓ1 with O(√(r)) average distortion. A consequence of this result is that the integrality gap of the well-known Goemans-Linial SDP relaxation for the Uniform Sparsest Cut problem is O(√(r)) on graphs G whose r-th smallest normalized eigenvalue of the Laplacian satisfies λr(G)/n ≥ Ω(1)ΦSDP (G). Our result improves upon the previously known bound of O(r) on the average distortion, and the integrality gap of the Goemans-Linial SDP under the same preconditions, proven in the previous works of [Deshpande and Venkat, 2014] and [Deshpande, Harsha and Venkat, 2016].