Approximation Algorithms for Broadcast Scheduling
Nikhil Bansal
IBM T. J. Watson Research Center
Friday, September 29th, 2006, 3:30 pm
Wean Hall 7220
Abstract
We consider the following problem in the broadcast scheduling model. 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 a poly-logarithmic approximation ratio for this problem, that improves upon the previously known bound of O(n^{1/2}).
This is joint work with Don Coppersmith and Maxim Sviridenko.
SPEAKER: Michael Dinitz
TIME: Wednesday 12-1pm, September 27, 2006
PLACE: NSH 1507
TITLE: Spanners with Slack
ABSTRACT:
Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion; spanners have been widely studied in the literature for over two decades, and a variety of tight results are known. For instance, it is known that any metric has a spanner with O(n) edges that approximates distances to within an O(log n) distortion.
In this talk we study the problem of spanners with slack: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a constant fraction of the distances, but are then required to incur only a constant (independent of n) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into L_p spaces. For instance, we show that if we ignore an epsilon fraction of the distances, we can get spanners with O(n) edges and O(log(1/epsilon)) distortion for the remaining distances.
Among other results in this talk, we show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. Finally, we also review notions of average distortion (without slack) previously studied in the literature, and show that our slack spanner constructions give us constant average distortion spanners.
This is joint work with Hubert Chan and Anupam Gupta
34 Years of Bin Packing
David S. Johnson
AT&T Labs
Friday, September 29, 2006
10:30am - SENSQ 5317
Abstract
In the bin packing problem, one is given a list of 1-dimensional items and asked to pack them into a minimum number of unit-capacity bins. This was one of the first NP-hard problems to be studied from the “approximation algorithm” point of view, and over the years it has served as a laboratory for the study of new questions about approximation algorithms and the development of new techniques for their analysis. In this talk I present a brief survey of this history, covering worst-case, average-case, and experimental results, and leading to the new “sum-of-squares” algorithm for the problem.
