Campus Event Calendar
Event Entry
What and Who
Covering selfish machines
Rob van Stee
Universtät Karlsruhe
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 12 January 2007
13:00
-- Not specified --
E1 4
024
Saarbrücken
Abstract
We consider the machine covering problem for selfish related
machines. For a constant number of machines, m, we show a
monotone polynomial time approximation scheme (PTAS) with running
time that is linear in the number of jobs. It uses a new
technique for reducing the number of jobs while remaining close
to the optimal solution. We also present an FPTAS for the classical
machine covering problem (the previous best result was a PTAS)
and use this to give a monotone FPTAS.
Additionally, we give a monotone approximation algorithm with
approximation ratio min(m,(2+\eps)s_1/s_m) where \eps>0 can
be chosen arbitrarily small and s_i is the (real) speed of
machine i. Finally we give improved results for two machines.
Our paper presents the first
results for this problem in the context of selfish machines.
Contact
--email hidden
passcode not visible
logged in users only
Ingrid Finkler, 01/11/2007 08:42
Ingrid Finkler, 01/09/2007 11:45 -- Created document.
Ingrid Finkler, 01/09/2007 11:45 -- Created document.