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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International