Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time

DOI10.1137/19M1244512zbMATH Open1479.90077arXiv1802.07439OpenAlexW3090692263MaRDI QIDQ5129231FDOQ5129231

Authors: Jatin Batra, Naveen Garg, Amit Kumar 

Publication date: 26 October 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1802.07439

Recommendations

• A polynomial time constant approximation for minimizing total weighted flow-time
• Fixed-parameter approximation schemes for weighted flowtime
• Minimizing weighted flow time
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• Algorithms for minimizing weighted flow time

zbMATH Keywords

dynamic programmingschedulingmulticut

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Cites Work

• Title not available (Why is that?)
• Speed is as powerful as clairvoyance
• Weighted geometric set cover via quasi-uniform sampling
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• A unified approach to approximating resource allocation and scheduling
• On column-restricted and priority covering integer programs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• LATIN 2004: Theoretical Informatics
• Minimizing weighted flow time
• Algorithms for minimizing weighted flow time
• Approximation algorithms for average stretch scheduling
• Approximation schemes for preemptive weighted flow time
• The geometry of scheduling
• Title not available (Why is that?)
• A polynomial time constant approximation for minimizing total weighted flow-time
• Fair scheduling via iterative quasi-uniform sampling
• On capacitated set cover problems

Cited In (3)

• A PTAS for minimizing weighted flow time on a single machine
• A polynomial time constant approximation for minimizing total weighted flow-time
• Title not available (Why is that?)

This page was built for publication: Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5129231)