[Apologies for multiple postings]

**************************************************
*
*    SANG/GRAND Seminar
*    http://cs.gmu.edu/~jmlien/seminar/
*
*    Tuesday, March 03, 2008. 12:00 pm
*    Room 430A ST2
*
**************************************************

*Title*

Online Scheduling of Packets with Deadlines in a Bounded Buffer

*Speaker*

Fei Li
Assistant Professor
Department of Computer Science
George Mason University


*Abstract*

Motivated by the Quality-of-Service buffer management problem, we
consider online scheduling of packets with deadlines in a size-bounded
buffer. This model is called bounded-buffer model. Time is discrete.
Packets arrive at a buffer over time. Each packet p has an integer
release time r_p, a non-negative value w_p, and an integer deadline d_p.
d_p specifies the time by which p should be sent. If p is transmitted by
its deadline d_p, p contributes our objective its value w_p. At any
time, the buffer can store no more than b packets. In each time step, at
most one packet can be sent. This model is preemptive: packets already
existing in the buffers can be dropped at any time before they are sent
and the dropped packet cannot be delivered any more. Our objective is to
maximize the total value of the packets sent by their deadlines. This
bounded-buffer model generalizes the bounded-delay model proposed in
(INFOCOM 00, CISS 01, STOC 01) in which the buffer's size b is assumed
larger than any packet's slack time (a packet p's slack time is defined
as d_p - r_p).

In SWAT 06, Azar and Levy consider a model called multi-buffer model
with multiple size-bounded buffers. The lower bound of competitive ratio
1.618 (INFOCOM 00, CISS 01, Algorithmica 03) for the bounded-delay model
applies to the multi-buffer model. The authors (Azar and Levy, SWAT
2006) developed a deterministic 9.82-competitive algorithm which applies
to the bounded-buffer model as well.

For the bounded-buffer model, we present a deterministic 3-competitive
online algorithm and a randomized 2.618-competitive online algorithm. We
also show that the lower bound of competitive ratio for a broad family
of deterministic algorithms is improved from 1.618 to 2.


*Short Bio*

Dr. Fei Li is an assistant professor at Computer Science Department of
George Mason University since Fall 2007. His major research interests
are online algorithms, approximation algorithms, randomized algorithms
and online learning algorithms. He got his PhD in February 2008 from
Columbia University, in computer science.


-- 
---------------------------------------------------------------
Jyh-Ming Lien
Assistant Professor
Department of Computer Science       [log in to unmask]
George Mason University, MSN 4A5     http://cs.gmu.edu/~jmlien
Fairfax, VA, 22030, USA              tel: +1-703-993-9546
---------------------------------------------------------------