A (2 + ε)-approximation algorithm for preemptive weighted flow time on a single machine

A. Wiese, Lars Rohwedder

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions.

The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time.

It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2+ε. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to Demand MultiCut on trees and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1+ε, and then solve its resulting instances up to a factor of 2+ε by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods.

We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.
Original languageEnglish
Title of host publicationSTOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021
Subtitle of host publication[Proceedings]
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherACM
Pages1042-1055
Number of pages14
ISBN (Electronic)9781450380539
DOIs
Publication statusPublished - Jun 2021

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Fingerprint

Dive into the research topics of 'A (2 + ε)-approximation algorithm for preemptive weighted flow time on a single machine'. Together they form a unique fingerprint.

Cite this