Milind Prabhu

The classic power of two choices phenomenon says that when placing $n$ balls into $n$ bins, sampling two uniformly random bins for each ball and placing it in the less-loaded one keeps the maximum load across bins below $O(\log\log n)$.

We ask what happens when the two choices come from an arbitrary, possibly highly non-uniform distribution over bins. We observe that in this setting, surprisingly, the greedy strategy fails badly! The main contribution is a different algorithm that still keeps the maximum load within an $O(\log\log n)$ factor of the best possible.

Standard coresets preserve the cost of every possible clustering solution, which can force pessimistic size bounds. We introduce approximation-preserving coresets, which focus on preserving good solutions and help explain why much smaller coresets often work well in practice.

Coresets compress a large k-means instance into a small weighted sample that preserves the clustering objective. We show that sensitivity sampling achieves nearly optimal bounds for constructing k-means coresets, both in worst-case instances and in well-clustered data.

A set of binary strings is hidden. Each query is another binary string, and the response is whichever hidden string is closest in Hamming distance. How many queries are needed to recover the full hidden set? This simple question is wide open; we make partial progress on it.

In classical makespan minimization, the goal is to assign jobs to machines so that no machine receives too much total load. We study a broad generalization where each machine measures its load using a different norm. While many special cases admit good approximation algorithms, we show that the general problem is much harder.

The Greenwald-Khanna algorithm estimates quantiles in a data stream using little memory. We extend it to weighted streams, where each item may stand for many copies, without explicitly expanding those copies.