A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time Article Swipe

MAKE IMPACT

Armbruster, Alexander , Rohwedder, Lars , Wiese, Andreas · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2511.16536

We study the general scheduling problem (GSP) which generalizes and unifies several well-studied preemptive single-machine scheduling problems, such as weighted flow time, weighted sum of completion time, and minimizing the total weight of tardy jobs. We are given a set of jobs with their processing times and release times and seek to compute a (possibly preemptive) schedule for them on one machine. Each job incurs a cost that depends on its completion time in the computed schedule, as given by a separate job-dependent cost function for each job, and our objective is to minimize the total resulting cost of all jobs. The best known result for GSP is a polynomial time $O(\log\log P)$-approximation algorithm [Bansal and Pruhs, FOCS 2010, SICOMP 2014]. We give a quasi-polynomial time $(2+ε)$-approximation algorithm for GSP, assuming that the jobs' processing times are quasi-polynomially bounded integers. For the special case of the weighted tardiness objective, we even obtain an improved approximation ratio of $1+ε$. For this case, no better result had been known than the mentioned $O(\log\log P)$-approximation for the general case of GSP. Our algorithms use a reduction to an auxiliary geometric covering problem. In contrast to a related reduction for the special case of weighted flow time [Rohwedder, Wiese, STOC 2021][Armbruster, Rohwedder, Wiese, STOC 2023] for GSP it seems no longer possible to establish a tree-like structure for the rectangles to guide an algorithm that solves this geometric problem. Despite the lack of structure due to the problem itself, we show that an optimal solution can be transformed into a near-optimal solution that has certain structural properties. Due to those we can guess a substantial part of the solution quickly and partition the remaining problem in an intricate way, such that we can independently solve each part recursively.

Type

preprint

Landing Page

https://doi.org/10.48550/arxiv.2511.16536

OA Status

green

OpenAlex ID

https://openalex.org/W7106316980

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7106316980

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2511.16536

Digital Object Identifier

Title

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time

Work title

Type

preprint

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-11-20

Full publication date if available

Authors

Armbruster, Alexander, Rohwedder, Lars, Wiese, Andreas

List of authors in order

Landing page

https://doi.org/10.48550/arxiv.2511.16536

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://doi.org/10.48550/arxiv.2511.16536

Direct OA link when available

Concepts

Tardiness, Mathematical optimization, Mathematics, Scheduling (production processes), Algorithm, Bounded function, Minimum-cost flow problem, Approximation algorithm, Reduction (mathematics), Time complexity, Job shop scheduling, Single-machine scheduling, Schedule, Computer science, Maximum flow problem, Set (abstract data type), Function (biology), Flow shop scheduling, Due date, Linear programming, Discrete mathematics, Deterministic algorithm, Minification, Online algorithm, Dynamic programming, Out-of-kilter algorithm, Efficient algorithm, Flow (mathematics), Flow network

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload