Campus Event Calendar
Event Entry
What and Who
A Lower Bound for Scheduling Mechanisms
Giorgos Christodoulou
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 7 March 2007
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
We study the mechanism design problem of scheduling tasks on $n$
unrelated machines in which the machines are the players of the
mechanism. The problem was proposed and studied in the seminal paper
of Nisan and Ronen, where it was shown that the approximation ratio of
mechanisms is between 2 and $n$.
We improve the lower bound to
$1+\sqrt{2}$ for 3 or more machines.
Contact
Giorgos Christodoulou
--email hidden
passcode not visible
logged in users only
Giorgos Christodoulou, 02/23/2007 12:06
Giorgos Christodoulou, 02/23/2007 12:02 -- Created document.
Giorgos Christodoulou, 02/23/2007 12:02 -- Created document.