Improved Approximation Algorithms for Non-preemptive Throughput Maximization

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 + ε ≈ 1.551 + ε [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 + ε for any constant ε > 0. Using pseudo-polynomial time (nT ) O(1) , we improve the factor even further to 5/4 + ε.

Our results extend to the setting in which we are given an arbitrary number of (identical) machines.