1 citations · 1 across the 10 of their papers we have counts for
4 papers · 1 filter
Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals
Sara Ahmadian, Edith Cohen, Mohammad Roghani
Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matchi…
Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch
Edith Cohen, Elena Gribelyuk, Pasin Manurangsi +1
In online facility location, points arrive one at a time, and the algorithm must either open a facility at the arriving point or route the point to an existing facility. The Meyers…
Stochastic Matching via Local Sparsification
Sara Ahmadian, Edith Cohen, Mohammad Roghani
The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride…
Adaptively Robust Resettable Streaming
Edith Cohen, Elena Gribelyuk, Jelani Nelson +1
We study algorithms in the resettable streaming model, where the value of each key can either be increased or reset to zero. The model is suitable for applications such as active r…