3 citations · 3 across the 4 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017
The Bane of Low-Dimensionality Clustering
Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg +1
In this paper, we give a conditional lower bound of on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even i…
cs.GT2017★ 3 cited
Makespan Minimization via Posted Prices
Michal Feldman, Amos Fiat, Alan Roytman
We consider job scheduling settings, with multiple machines, where jobs arrive online and choose a machine selfishly so as to minimize their cost. Our objective is the classic make…