[Colloquium] TTIC Talks: Sungjim Im, UIUC

[Liv Leader]

When:     Thursday, February 2 @ 11 a.m.

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

Who:      Sungjim Im, UIUC

Title:      Broadcast scheduling and its submodular extension

In broadcast scheduling, there is a server that stores pages of data,
and requests arrive for pages. When the server broadcasts a page, all
outstanding requests are satisfied simultaneously. Hence, in certain
applications such as wireless and LAN networks, broadcast scheduling
can be a useful way of disseminating shared data across clients.
Natural extensions of broadcast scheduling have a variety of
applications and raise interesting algorithmic questions.

We study broadcast scheduling both in the online and offline settings.
In the online setting, we give the first scalable algorithm for
minimizing the average response time of jobs, resolving a long
standing open problem in this area. We will briefly discuss the
technical tools developed in resolving this question that have led to
several other results in online scheduling. In the offline setting, we
discuss a generalization of broadcast scheduling where each client's
satisfaction is measured as a submodular function of the transmitted
pages. This generalization has interesting applications to web page
ranking and stochastic query problems in databases.

Host: Julia Chuzhoy, cjulia at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120126/b74c6bf2/attachment.htm