{"ID":2823804,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.25020","arxiv_id":"2512.25020","title":"Approximation Algorithms for Fair Repetitive Scheduling","abstract":"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.","short_abstract":"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 compl...","url_abs":"https://arxiv.org/abs/2512.25020","url_pdf":"https://arxiv.org/pdf/2512.25020v1","authors":"[\"Danny Hermelin\",\"Danny Segev\",\"Dvir Shabtay\"]","published":"2025-12-31T18:17:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}