3 papers
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…
cs.GT2015
Pricing Online Decisions: Beyond Auctions
Ilan Reuven Cohen, Alon Eden, Amos Fiat +1
We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of ma…