BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Online Stochastic Scheduling using Posted Prices Chawla, Shuchi


We consider a scheduling problem where jobs drawn from a distribution arrive over time and scheduling decisions must be made in an online fashion. The scheduler's goal is to maximize the total value of scheduled jobs. We focus on designing posted price based algorithms -- at every point of time, the algorithm specifies prices for different starting times and job lengths, and the arriving job chooses where to get placed. This model is related but not identical to prophet inequalities. I will present upper and lower bounds on the competitive ratio of pricing based algorithms. I will also describe an intriguing open question.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International