23 citations · 24 across the 2 of their papers we have counts for
Showing 2011 · cs.DSShow all
2 papers · 2 filters
cs.DS2011★ 23 cited
Min-Max Graph Partitioning and Small Set Expansion
Nikhil Bansal, Uriel Feige, Robert Krauthgamer +5
We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maxi…
cs.DS2011★ 1 cited
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Nikhil Bansal, Niv Buchbinder, Aleksander Madry +2
We give the first polylogarithmic-competitive randomized online algorithm for the -server problem on an arbitrary finite metric space. In particular, our algorithm achieves a co…