TECHNION OR SEMINAR 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 <Or-seminar@technion.ac.il> <http://iemm1.technion.ac.il/mailman/listinfo/or-seminar> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Elad Hazan <ehazan@ie.technion.ac.il>