32 citations · 47 across the 25 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
Polylogarithmic Bounds on the Competitiveness of Min-cost (Bipartite) Perfect Matching with Delays
Yossi Azar, Ashish Chiplunkar, Haim Kaplan
We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) recently introduced by Emek et al, (STOC 2016). This problem is defined on an underlying -point me…
cs.GT2016
When should an expert make a prediction?
Amir Ban, Yossi Azar, Yishay Mansour
We consider a setting where in a known future time, a certain continuous random variable will be realized. There is a public prediction that gradually converges to its realized val…
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…