5 papers
A Refined Approximation for Euclidean k-Means
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani +2
In the Euclidean -Means problem we are given a collection of points in an Euclidean space and a positive integer . Our goal is to identify a collection of points…
Planted Models for -way Edge and Vertex Expansion
Anand Louis, Rakesh Venkat
Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a…
Semi-Random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
Anand Louis, Rakesh Venkat
The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph a…
Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces
Yuval Rabani, Rakesh Venkat
We consider the problem of embedding a finite set of points that satisfy triangle inequalities into , when the points are…
On Fortification of Projection Games
Amey Bhangale, Ramprasad Saptharishi, Girish Varma +1
A recent result of Moshkovitz \cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection g…