[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~

THEORY SEMINAR!

~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
Tuesday, January 22, 2013
3:00 p.m.
Ryerson 251
 
Benjamin Moseley
University of Chicago, TTIC 
ttic.uchicago.edu/~moseley
 
Title: “Online Scheduling with General Cost Functions”
 
Abstract: In this talk we will consider a new general online scheduling problem where the goal is to minimize sum_j w_j g(F_j), where w_j is the weight/importance of job J_j, F_j is the flow time of the job in the schedule, and g is an arbitrary non-decreasing cost function. Numerous natural scheduling objectives are special cases of this general framework. We show that the scheduling algorithm Highest Density First (HDF) is (2+epsilon)-speed O(1) competitive for all cost functions g simultaneously. We give lower bounds that show the HDF algorithm and this analysis are essentially optimal. Finally, we show scalable algorithms are achievable in some special cases.
 
This is joint work with Kirk Pruhs and Sungjin Im and appeared in SODA 2012.
 
Host: Prof. Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 251