57 citations · 245 across the 48 of their papers we have counts for
4 papers · 1 filter
Metric Distortion Bounds for Randomized Social Choice
Moses Charikar, Prasanna Ramakrishnan
Consider the following social choice problem. Suppose we have a set of voters and candidates that lie in a metric space. The goal is to design a mechanism to choose a candi…
Near-Optimal Explainable -Means for All Dimensions
Moses Charikar, Lunjia Hu
Many clustering algorithms are guided by certain cost functions such as the widely-used -means cost. These algorithms divide data points into clusters with often complicated bou…
Multiway Online Correlated Selection
Guy Blanc, Moses Charikar
We give a -competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was due to Fahrbach, Huang, Tao, and Za…
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization
Moses Charikar, Lunjia Hu
In the non-negative matrix factorization (NMF) problem, the input is an matrix with non-negative entries and the goal is to factorize it as . The $m\ti…