[Colloquium] REMINDER: Talks at TTIC tomorrow at Noon-Shi Li

[Dawn Ellis]

When:     Friday, October 25th at Noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Who:       Shi Li

Title:       Better Algorithms and Hardness for Broadcast Scheduling via a
              Discrepancy Approach

Abstract :

In this talk, I will present our new result on approximating broadcast
scheduling problem. In the problem, there is a single server that can hold
$n$ pages of unit size, and multiple requests for these pages arrive over
time. At each time slot the server can broadcast one page which satisfies
all the outstanding requests for this page at that time.
The goal is to find a schedule to minimize the average response time of the
requests, i.e. the duration since a request arrives until it is satisfied.

We give an $\tilde{O}(\log^{1.5} n)$ approximation algorithm for the
problem improving upon the previous $\tilde{O}(\log^2 n)$ approximation. We
also show an $\Omega(\log^{1/2-\eps} n)$ hardness result, and an
integrality gap of $\Omega(\log n)$ for the natural LP relaxation for the
problem. Prior to our work, only NP-Hardness and a (tiny) constant
integrality gap was known.

These results are based on establishing a close connection to the
discrepancy minimization problem for permutation set-systems. Specifically,
our improved approximation is based on using recent algorithmic ideas
developed for discrepancy minimization. Our integrality gap is obtained
from the $\Omega(\log n)$-lower bound on the discrepancy of 3-permutations,
while our hardness result is based on establishing the first hardness
result for the discrepancy of $\ell$-permutations.

Based on joint work with Nikhil Bansal, Moses Charikar and Ravishankar
Krishnaswamy. Paper to appear in SODA 2014.




***************************************
Research at TTIC Seminar Series

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at
mcallester at ttic.edu


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131024/5eb6fbbd/attachment.htm