[Colloquium] Research at TTIC: Shi Li
Dawn Ellis
dellis at ttic.edu
Fri Apr 11 08:16:03 CDT 2014
When: Friday, April 18th at noon
Where: TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526
Who: Shi Li, TTIC Research Assistant Professor
Title: A Dynamic Programming Framework for Non-Preemptive Scheduling
Problems on Multiple Machines
Abstract:
In this talk, I will talk about our recent results about a variety of
non-preemptive scheduling problems. The central problem is machine
minimization problem, where we are given a set of $n$ jobs, each job $J$
with an arrival time $r_J$, a deadline $d_J$ and a processing time $p_J$.
The goal is to schedule all the $n$ jobs non-preemptively in minimum number
of machines. To schedule a job $J$, we need to select a job interval of
length $p_J$ contained in $(r_J, d_J)$. Two jobs can be scheduled in the
same machine if their intervals do not overlap.
We develop a novel quasi-polynomial time dynamic programming framework that
gives a $1+\eps$-speed 2-approximation and a $2+\eps$-speed 1-approximation
for the problem. An $s$-speed $\alpha$-approximation is an algorithm which
schedules all jobs in $\alpha \cdot opt$ machines of speed $s$, where $opt$
is the minimum number of $1$-speed machines required to schedule all jobs.
These are the first O(1)-speed O(1)-approximation algorithms for the
problem. Our dynamic programming framework also leads many improved
algorithms with speed augmentation. The problems include maximizing
throughput, minimizing flow time, minimizing tardiness and the weighted
versions of these problems.
Based on joint work with Sungjin Im, Benjamin Moseley and Eric Torng
***************************************
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/20140411/10ab9a20/attachment.htm
More information about the Colloquium
mailing list