12 citations · 27 across the 12 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.DS2011
Approximating Non-Uniform Sparsest Cut via Generalized Spectra
Venkatesan Guruswami, Ali Kemal Sinop
We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any , given cost and demand graphs with edge weights respecti…
cs.CC2011
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives
Venkatesan Guruswami, Ali Kemal Sinop
We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This…
cs.DS2011
Optimal Column-Based Low-Rank Matrix Reconstruction
Venkatesan Guruswami, Ali Kemal Sinop
We prove that for any real-valued matrix , and positive integers , there is a subset of columns of such that projecting onto their span…