Approximation Algorithms for Fair Repetitive Scheduling
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918267150401536 |
|---|---|
| author | Hermelin, Danny Segev, Danny Shabtay, Dvir |
| author_facet | Hermelin, Danny Segev, Danny Shabtay, Dvir |
| contents | We consider a recently introduced fair repetitive scheduling problem involving a set of clients, each asking for their associated job to be daily scheduled on a single machine across a finite planning horizon. The goal is to determine a job processing permutation for each day, aiming to minimize the maximum total completion time experienced by any client. This problem is known to be NP-hard for quite restrictive settings, with previous work offering exact solution methods for highly-structured special cases.
In this paper, we focus on the design of approximation algorithms with provable performance guarantees. Our main contributions can be briefly summarized as follows:
(i) When job processing times are day-dependent, we devise a polynomial-time LP-based $2$-approximation, as well as a polynomial-time approximation scheme for a constant number of days.
(ii) With day-invariant processing times, we obtain a surprisingly simple $(\frac{1+\sqrt{2}}{2}+ε)$-approximation in polynomial time. This setting is also shown to admit a quasi-polynomial-time approximation scheme for an arbitrary number of days.
The key technical component driving our approximation schemes is a novel batching technique, where jobs are conceptually grouped into batches, subsequently leading either to a low-dimensional dynamic program or to a compact configuration LP. Concurrently, while developing our constant-factor approximations, we propose a host of lower-bounding mechanisms that may be of broader interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_25020 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for Fair Repetitive Scheduling Hermelin, Danny Segev, Danny Shabtay, Dvir Data Structures and Algorithms We consider a recently introduced fair repetitive scheduling problem involving a set of clients, each asking for their associated job to be daily scheduled on a single machine across a finite planning horizon. The goal is to determine a job processing permutation for each day, aiming to minimize the maximum total completion time experienced by any client. This problem is known to be NP-hard for quite restrictive settings, with previous work offering exact solution methods for highly-structured special cases. In this paper, we focus on the design of approximation algorithms with provable performance guarantees. Our main contributions can be briefly summarized as follows: (i) When job processing times are day-dependent, we devise a polynomial-time LP-based $2$-approximation, as well as a polynomial-time approximation scheme for a constant number of days. (ii) With day-invariant processing times, we obtain a surprisingly simple $(\frac{1+\sqrt{2}}{2}+ε)$-approximation in polynomial time. This setting is also shown to admit a quasi-polynomial-time approximation scheme for an arbitrary number of days. The key technical component driving our approximation schemes is a novel batching technique, where jobs are conceptually grouped into batches, subsequently leading either to a low-dimensional dynamic program or to a compact configuration LP. Concurrently, while developing our constant-factor approximations, we propose a host of lower-bounding mechanisms that may be of broader interest. |
| title | Approximation Algorithms for Fair Repetitive Scheduling |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.25020 |