Moses Charikar

most citedLimits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

4 citations · 4 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2014

Online Bipartite Matching with Decomposable Weights

Moses Charikar, Monika Henzinger, Huy L. Nguyen

We study a weighted online bipartite matching problem: $G (V_{1}, V_{2}, E)$ is a weighted bipartite graph where $V_{1}$ is known beforehand and the vertices of $V_{2}$ arrive online. The g…

cs.DS2010

Vertex Sparsifiers and Abstract Rounding Algorithms

Moses Charikar, Tom Leighton, Shi Li +1

The notion of vertex sparsification is introduced in \cite{M}, where it was shown that for any graph $G = (V, E)$ and a subset of $k$ terminals $K \subset V$ , there is a polynomial…

cs.CC2010★ 4 cited

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

Prahladh Harsha, Moses Charikar, Matthew Andrews +14

These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-2…