Speaker: Asaf Levin
Title: A Unified Approach to Truthful Scheduling on Related Machines
Date: Mon, October 22,  12:30-13:30
Venue: Bloomfield 527
Description: We present a unified framework for designing deterministic
monotone polynomial time approximation schemes (PTAS's) for a wide
class of scheduling problems on uniformly related machines. This
class includes (among others) minimizing the makespan, maximizing the
minimum load, and minimizing the l_p norm of the machine loads
vector. Previously, this kind of result was only known for the
makespan objective. Monotone algorithms have the property that an
increase in the speed of a machine cannot decrease the amount of work
assigned to it. Monotone approximation schemes have an important role
in the emerging area of algorithmic mechanism design. In the
game-theoretical setting of these scheduling problems there is a
social goal, which is one of the objective functions that we study.
Each machine is controlled by a selfish single-parameter agent, where
its private information is its cost of processing a unit sized job,
which is also the inverse of the speed of its machine. Each agent
wishes to maximize its own profit, defined as the payment it receives
from the mechanism minus its cost for processing all jobs assigned to
it, and places a bid which corresponds to its private information.
Based on a joint work with L. Epstein and R. van Stee to appear in
Proc. SODA ' 2013. During the talk I will present all the necessary
background, and I will try to make it as self-contained as possible.
Or-seminar mailing list
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Elad Hazan   <>