The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                               Reuven Bar-Yehuda
                         Department of Computer Science
                                Technion, Haifa


                                 will speak on


            A Unified Approach to Approximating Resource Allocation
                                 and Scheduling

Abstract:
We present a general framework for solving resource allocation and scheduling
problems. Given a resource of fixed size, we present algorithms that
approximate the maximum throughput or the minimum loss by a constant factor.
Our approximation factors apply to many problems, among which are:

(i) real-time scheduling of jobs on parallel machines;

(ii) bandwidth allocation for sessions between two endpoints;

(iii) general caching;

(iv) dynamic storage allocation;

(v) bandwidth allocation on optical line and ring topologies.

For some of these problems we provide the first constant factor approximation
algorithm. Our algorithms are simple and efficient. They use the local-ratio
technique and can be equivalently interpreted within the primal-dual schema.

Joint work with:  Amotz Bar-Noy, Ari Freund, Joseph Naor, and Baruch Schieber.





                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                           on Monday, March 13, 2000
                                    at 14:30