Showing cs.DSShow all
3 papers · 1 filter
cs.DS2020
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…
cs.DS2019
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…
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…