3 papers
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
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…
cs.DS2016
Online Lower Bounds via Duality
Yossi Azar, Ilan Reuven Cohen, Alan Roytman
In this paper, we exploit linear programming duality in the online setting (i.e., where input arrives on the fly) from the unique perspective of designing lower bounds on the compe…