8 papers
Prophet Inequality with Conservative Prediction
Johannes Brüstle, Ilan Reuven Cohen, Stefano Leonardi
Prophet inequalities compare online stopping strategies against an omniscient "prophet" using distributional knowledge. In this work, we augment this model with a conservative pred…
A General Framework for Learning-Augmented Online Allocation
Ilan Reuven Cohen, Debmalya Panigrahi
Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimi…
Weighted completion time minimization for capacitated parallel machines
Ilan Reuven Cohen, Izack Cohen, Iyar Zaks
We consider the weighted completion time minimization problem for capacitated parallel machines, which is a fundamental problem in modern cloud computing environments. We study set…
An Asymptotic Lower Bound for Online Vector Bin Packing
Nikhil Bansal, Ilan Reuven Cohen
We consider the online vector bin packing problem where items specified by -dimensional vectors must be packed in the fewest number of identical -dimensional bins. Azar e…
Tight Bounds for Online Edge Coloring
Ilan Reuven Cohen, Binghui Peng, David Wajc
Vizing's celebrated theorem asserts that any graph of maximum degree admits an edge coloring using at most colors. In contrast, Bar-Noy, Naor and Motwani showed over a qu…
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…