Title	Online Stochastic Scheduling using Posted Prices
Creator	Chawla, Shuchi
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2017-11-15T11:34
Description	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.
Extent	34 minutes
Subject	Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: University of Wisconsin-Madison
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2018-05-15
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0366309
URI	http://hdl.handle.net/2429/65877
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos