### DIMACS Theoretical Computer Science Seminar

Title: Improved approximation algorithms for broadcast scheduling

Speaker: **Ravishankar Krishnaswamy**, CMU

Date: Wednesday, April 10, 2013 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In the classical broadcast scheduling problem, there are n pages stored
at a server, and there are a set of m requests for these pages over time. The server
can broadcast one page every time unit, and that broadcast satisfies all the requests
for the page which have arrived before this broadcast. The goal is to compute the
broadcast sequence at the server which minimizes the average response time of the
requests, where the response time of a request is the earliest subsequent time the
server broadcasts the page associated with the request.

Following a long line of work, the best known algorithm for this problem achieves an
approximation factor of O(log^2 n), due to Bansal, Coppersmith and Sviridenko [BCS05].
In this talk, we present an improved algorithm with approximation of O(log^1.5 n).
From a technical point of view, our algorithm utilizes the recent rounding techniques
due to Lovett and Meka to achieve a more fine grained control over the error incurred
at each step of the randomized rounding procedure, which results in this improvement.
As a bi-product, our rounding algorithm immediately gives insights into the first
non-trivial integrality gaps for the natural LP relaxation as well.

Joint work with Nikhil Bansal, Moses Charikar, and Shi Li.

See: http://paul.rutgers.edu/~yixinxu/theory-spring13.html