Online Set Packing and Competitive Scheduling of Multi-Part Tasks

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.