Campus Event Calendar

Event Entry

New for: D3

What and Who

Online Set Packing and Competitive Scheduling of Multi-Part Tasks

Dror Rawitz
Tel-Aviv University
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS  
AG Audience

Date, Time and Location

Friday, 16 April 2010
45 Minutes
E1 4


We consider a scenario where large data frames are broken into a few packets and

transmitted over the network. Our focus is on a bottleneck router: the model
assumes that in each time step, a set of packets (a burst) arrives, from which
only one packet can be served, and all other packets are lost. A data frame is
considered useful only if none of its constituent packets is lost, and otherwise
it is worthless. We abstract the problem as a new type of online set packing,
present a randomized distributed algorithm and a matching lower bound on the
competitive ratio for any randomized online algorithm. Our bounds are expressed
in terms of the maximal burst size and the maximal number of packets per frame.
We also present refined bounds that depend on the uniformity of these parameters.

Joint work with Emek, Halldorsson, Mansour, Patt-Shamir and Radhakrishnan.


Julian Mestre
--email hidden
passcode not visible
logged in users only

Julian Mestre, 03/31/2010 10:19 -- Created document.