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


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