Colloquia, Seminars and Conference News
Title : Approximation algorithms for Broadcast Scheduling
Date : April 21, 2006. (2:00 pm) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Nikhil Bansal
Abstract:
We consider the following well-studied model for broadcast scheduling. There are n pages at a broadcast server, and at each time slot the server receives several requests for these pages. The server can transmit exactly one page per time slot, and once a page is transmitted, it satisfies all the requests waiting for that page. The goal is to find a broadcast schedule that minimizes the average waiting time of requests.
I will describe an algorithm with a poly-logarithmic approximation ratio
for this problem. This is joint work with Don Coppersmith and Maxim
Sviridenko.
Bio:
Nikhil Bansal is a Research Staff Member in the Theory of Computation
group at IBM T.J. Watson Research Labs. He obtained his PhD in 2003
from Carnegie Mellon University, and his Bachelor's degree in 1999
from Indian Institute of Technology, Bombay. His research interests
are broadly in the area of design and analysis of algorithms, with
particular focus on approximation and online algorithms.
[Back]
