English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

An important objective in scheduling literature is to minimize the sum ofweighted flow times. We are given a set of jobs where each job is characterizedby a release time, a processing time, and a weight. Our goal is to find apreemptive schedule on a single machine that minimizes the sum of the weightedflow times of the jobs, where the flow time of a job is the time between itscompletion time and its release time. The currently best known polynomial timealgorithm for the problem is a (2+eps)-approximation by Rohwedder and Wiese[STOC 2021] which builds on the prior break-through result by Batra, Garg, andKumar [FOCS 2018] who found the first pseudo-polynomial time constant factorapproximation algorithm for the problem, and on the result by Feige, Kulkarni,and Li [SODA 2019] who turned the latter into a polynomial time algorithm.However, it remains open whether the problem admits a PTAS. We answer thisquestion in the affirmative and present a polynomial time (1+eps)-approximationalgorithm for weighted flow time on a single machine. We rely on a reduction ofthe problem to a geometric covering problem, which was introduced in thementioned (2+eps)-approximation algorithm, losing a factor 1+eps in theapproximation ratio. However, unlike that algorithm, we solve the resultinginstances of this problem exactly, rather than losing a factor 2+eps. Key forthis is to identify and exploit structural properties of instances of thegeometric covering problem which arise in the reduction from weighted flowtime.

A PTAS for Minimizing Weighted Flow Time on a Single Machine