Sunday, March 12, 14:15-15:15
at 14:00
Schreiber Building, Room 309
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.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html