2018/02/21 by Jatin Batra, Naveen Garg, Batra, Jatin +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1802.07439
openalex publication_date 2018/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the weighted flow-time problem on a single machine, we are given a set of\nn jobs, where each job has a processing requirement pj, release date rj and\nweight wj. The goal is to find a preemptive schedule which minimizes the sum\nof weighted flow-time of jobs, where the flow-time of a job is the difference\nbetween its completion time and its released date. We give the first\npseudo-polynomial time constant approximation algorithm for this problem. The\nrunning time of our algorithm is polynomial in n, the number of jobs, and P,\nwhich is the ratio of the largest to the smallest processing requirement of a\njob. Our algorithm relies on a novel reduction of this problem to a\ngeneralization of the multi-cut problem on trees, which we call the Demand\nMulti-Cut problem. Even though we do not give a constant factor approximation\nalgorithm for the Demand Multi-Cut problem on trees, we show that the specific\ninstances of Demand Multi-Cut obtained by reduction from weighted flow-time\nproblem instances have more structure in them, and we are able to employ\ntechniques based on dynamic programming. Our dynamic programming algorithm\nrelies on showing that there are near optimal solutions which have nice\nsmoothness properties, and we exploit these properties to reduce the size of DP\ntable.\n