Title: Algorithms for Minimizing Weighted Flow Time

We consider the following classical scheduling problem. Jobs arrive over time to be scheduled on a single machine. Each job has a processing time and a weight. We seek to minimize the sum of weighted flow times of the jobs. The flow time of a job is the overall time the job spends in the system from the time it arrives to the time its processing is completed. We allow preemption of jobs. The algorithm that at any time schedules the job with shortest remaining processing time (SRPT) is known to be optimal when all jobs have the same weight. However, no algorithms with sub-polynomial approximation ratios were known for the weighted problem. We present new on-line and off-line algorithms for the weighted problem that give much improved performance ratios and strongly suggest the possibility of an approximation scheme (ptas) for this problem. This is based on joint work with Sanjeev Khanna and An Zhu.