From: Tami Tamir (tami@cs.washington.edu)
Date: Wed Apr 14 2004 - 11:15:26 PDT
Next meeting of theory seminar 590z: Friday 4/16, 11:30-12:20, EE1-045.
Speaker: Tami Tamir
Title:Windows Scheduling as a Restricted Version of Bin Packing
Abstract:
Given a sequence of n positive integers w_1,w_2,..., w_n that are associated
with the items 1,2,...,n respectively. In the windows scheduling problem,
the goal is to schedule all the items (equal length information pages) on
broadcasting channels such that the gap between two consecutive appearances
of page i on any of the channels is at most w_i slots (a slot is the
transmission time of one page). In the unit fraction bin packing problem,
the goal is to pack all the items in bins of unit size where the size
(width) of item i is 1/w_i. The optimization objective is to minimize the
number of channels or bins.
In the off-line setting the sequence is known in advance whereas in the
on-line setting the items arrive in order and assignment decisions are
irrevocable. Since a page requires at least 1/w_i of a channel's bandwidth,
it follows that windows scheduling without migration (all broadcasts of a
page must be from the same channel) is a restricted version of unit
fractions bin packing.
The talk considers the relationship between windows-scheduling and
unit-fraction bin-packing, by presenting upper and lower bounds for each of
these problems in the online and offline settings.
Joint work with Amotz Bar-Noy and Richard Ladner.
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Wed Apr 14 2004 - 11:15:49 PDT