Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time.

In the weighted flow-time problem on a single machine, we are given a set ofn jobs, where each job has a processing requirement p_j, release date r_j andweight w_j. The goal is to find a preemptive schedule which minimizes the sumof weighted flow-time of jobs, where the flow-time of a job is the differencebetween its completion time and its released date. We give the firstpseudo-polynomial time constant approximation algorithm for this problem. Therunning time of our algorithm is polynomial in n, the number of jobs, and P,which is the ratio of the largest to the smallest processing requirement of ajob. Our algorithm relies on a novel reduction of this problem to ageneralization of the multi-cut problem on trees, which we call the DemandMulti-Cut problem. Even though we do not give a constant factor approximationalgorithm for the Demand Multi-Cut problem on trees, we show that the specificinstances of Demand Multi-Cut obtained by reduction from weighted flow-timeproblem instances have more structure in them, and we are able to employtechniques based on dynamic programming. Our dynamic programming algorithmrelies on showing that there are near optimal solutions which have nicesmoothness properties, and we exploit these properties to reduce the size of DPtable.