[Colloquium] REMINDER: Research at TTIC: Shi Li

[Dawn Ellis]

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/20140417/26be0fb7/attachment-0001.htm