Tel-Aviv University - Computer Science Colloquium
Sunday, December 27, 14:15-15:15
at 14:00 We consider problems of resource allocation, these are various models of on-line and off-line bin packing and scheduling. We measure the performance of on-line algorithms by the competitive ratio, and for off-line algorithms by the performance ratio. We give a lower bound for on-line vector covering which is linear in the dimension. We prove lower bounds on on-line scheduling with precedence constraints and on load balancing of temporary tasks, all for identical machines. The deterministic lower bounds for the two last problems match the upper bound of the well-known algorithm of Graham "List". We discuss on-line machine covering of both identical and related machines and show that randomization decreases the competitive ratio for identical machines. We mention on-line randomized scheduling on two related machines. We show that if one machine is at least twice faster than the other, it is best to use only the fast machine. Finally we state results for off-line scheduling problems. Here we give polynomial approximation schemes for covering related machines, and for scheduling in the L_p norm.
Ph.D. dissertation, work supervised by Yossi Azar.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html