  In the weighted flow-time problem on a single machine, we are given a set of
n jobs, where each job has a processing requirement p_j, release date r_j and
weight w_j. The goal is to find a preemptive schedule which minimizes the sum
of weighted flow-time of jobs, where the flow-time of a job is the difference
between its completion time and its released date. We give the first
pseudo-polynomial time constant approximation algorithm for this problem. The
running 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 a
job. Our algorithm relies on a novel reduction of this problem to a
generalization of the multi-cut problem on trees, which we call the Demand
Multi-Cut problem. Even though we do not give a constant factor approximation
algorithm for the Demand Multi-Cut problem on trees, we show that the specific
instances of Demand Multi-Cut obtained by reduction from weighted flow-time
problem instances have more structure in them, and we are able to employ
techniques based on dynamic programming. Our dynamic programming algorithm
relies on showing that there are near optimal solutions which have nice
smoothness properties, and we exploit these properties to reduce the size of DP
table.
