Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914434051473408 |
|---|---|
| author | Armbruster, Alexander Grandoni, Fabrizio Tinguely, Antoine Wiese, Andreas |
| author_facet | Armbruster, Alexander Grandoni, Fabrizio Tinguely, Antoine Wiese, Andreas |
| contents | The (Non-Preemptive) Throughput Maximization problem is a natural and fundamental scheduling problem. We are given $n$ jobs, where each job $j$ is characterized by a processing time and a time window, contained in a global interval $[0,T)$, during which~$j$ can be scheduled. Our goal is to schedule the maximum possible number of jobs non-preemptively on a single machine, so that no two scheduled jobs are processed at the same time. This problem is known to be strongly NP-hard. The best-known approximation algorithm for it has an approximation ratio of $1/0.6448 + \varepsilon \approx 1.551 + \varepsilon$ [Im, Li, Moseley IPCO'17], improving on an earlier result in [Chuzhoy, Ostrovsky, Rabani FOCS'01]. In this paper we substantially improve the approximation factor for the problem to $4/3+\varepsilon$ for any constant~$\varepsilon>0$. Using pseudo-polynomial time $(nT)^{O(1)}$, we improve the factor even further to $5/4+\varepsilon$. Our results extend to the setting in which we are given an arbitrary number of (identical) machines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_29451 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Approximation Algorithms for Non-Preemptive Throughput Maximization Armbruster, Alexander Grandoni, Fabrizio Tinguely, Antoine Wiese, Andreas Data Structures and Algorithms The (Non-Preemptive) Throughput Maximization problem is a natural and fundamental scheduling problem. We are given $n$ jobs, where each job $j$ is characterized by a processing time and a time window, contained in a global interval $[0,T)$, during which~$j$ can be scheduled. Our goal is to schedule the maximum possible number of jobs non-preemptively on a single machine, so that no two scheduled jobs are processed at the same time. This problem is known to be strongly NP-hard. The best-known approximation algorithm for it has an approximation ratio of $1/0.6448 + \varepsilon \approx 1.551 + \varepsilon$ [Im, Li, Moseley IPCO'17], improving on an earlier result in [Chuzhoy, Ostrovsky, Rabani FOCS'01]. In this paper we substantially improve the approximation factor for the problem to $4/3+\varepsilon$ for any constant~$\varepsilon>0$. Using pseudo-polynomial time $(nT)^{O(1)}$, we improve the factor even further to $5/4+\varepsilon$. Our results extend to the setting in which we are given an arbitrary number of (identical) machines. |
| title | Improved Approximation Algorithms for Non-Preemptive Throughput Maximization |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.29451 |