20 citations · 45 across the 23 of their papers we have counts for
3 papers · 1 filter
The Randomized -Server Conjecture is False!
Sébastien Bubeck, Christian Coester, Yuval Rabani
We prove a few new lower bounds on the randomized competitive ratio for the -server problem and other related problems, resolving some long-standing conjectures. In particular,…
Generalized Unrelated Machine Scheduling Problem
Shichuan Deng, Jian Li, Yuval Rabani
We study the generalized load-balancing (GLB) problem, where we are given jobs, each of which needs to be assigned to one of unrelated machines with processing times $\{p_{…
Shortest Paths without a Map, but with an Entropic Regularizer
Sébastien Bubeck, Christian Coester, Yuval Rabani
In a 1989 paper titled "shortest paths without a map", Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while att…