← Latest papers
💻 computer science

A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization

This paper presents a randomized (12/11+ε)(12/11+\varepsilon)-approximation algorithm for maximizing the number of scheduled jobs in unweighted nonpreemptive throughput maximization on identical machines, improving upon previous approximation factors of 4/3+ε4/3+\varepsilon and 17/13+ε17/13+\varepsilon.

Original author: Mikhail Cherniavskii, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev, Fedor Ozhegov, Alexander Shekhovtsov

Published 2026-11-19
📖 6 min read🧠 Deep dive

Original author: Mikhail Cherniavskii, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev, Fedor Ozhegov, Alexander Shekhovtsov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, a fundamental challenge involves organizing a stream of tasks to get as much work done as possible within a fixed timeframe. Imagine a factory floor with several identical machines, each capable of processing a single item at a time. Every item, or "job," arrives with a specific start time and a hard deadline by which it must be finished. Each job also requires a set amount of time to complete. The goal is not to finish every single job, but to select the largest possible number of them and arrange them on the machines so that no two jobs overlap on the same machine and every selected job finishes before its deadline. This is a problem of throughput maximization. It is deceptively simple to state but notoriously difficult to solve perfectly, especially when the number of jobs is large and their timing windows vary wildly. Because finding the absolute best schedule is often computationally impossible for large sets, researchers focus on creating algorithms that can quickly find a schedule that is very close to the best possible one. The measure of success is how many jobs the algorithm manages to schedule compared to the theoretical maximum.

For years, the best known methods for solving this problem on an arbitrary number of machines could guarantee a schedule containing roughly three-quarters of the optimal number of jobs. A team of researchers has now pushed this boundary significantly further. They have developed a new algorithm that, for any desired level of precision, can guarantee a schedule containing at least eleven-twelfths of the maximum possible number of jobs. This improvement, while seemingly small in fraction, represents a substantial leap in the theoretical limits of what is achievable for this class of scheduling problems. The method works by first creating a flexible, probabilistic blueprint of how jobs could be arranged, and then carefully converting that blueprint into a concrete, feasible schedule without losing too much value in the process.

The core difficulty in solving this problem lies in the nature of the jobs themselves. A single job might fit into many different time slots, but it can only be counted once in the final schedule. If a computer tries to guess where to place jobs by randomly picking from all possible valid slots, it often ends up with a messy result: some jobs might be selected multiple times in different places, while others are left out entirely. The researchers' approach begins by relaxing the rules slightly to allow a job to be "spread out" across several potential slots in a mathematical model. This model assigns probabilities to different arrangements, effectively saying, "There is a certain chance this job goes here, and a certain chance it goes there." The challenge is then to take this fuzzy, fractional picture and turn it into a real, solid schedule where every job is either fully present or fully absent, without violating the machine's capacity or the job's deadline.

To bridge the gap between the mathematical model and the real schedule, the team introduced a strategy that treats the timeline as a series of blocks. They group these blocks together and sample arrangements from a pre-calculated list of possibilities. The key innovation is how they handle the jobs that appear in multiple blocks. In their model, a job might appear at its start time in one block and at its end time in another. If the algorithm simply picks one of these appearances at random, it might accidentally pick both, creating a duplicate, or pick neither, losing the job entirely. The researchers designed a system to detect when a job is likely to be duplicated or missed and then "repair" the schedule. They identified specific pairs of jobs where one job's time slot could effectively serve as a backup for another. If a job is duplicated, the extra copy can be removed, and its time slot can be given to a different job that was missed, provided the timing allows it.

This repair mechanism relies on a careful accounting of probabilities. The algorithm tracks how likely a job is to be duplicated and how likely it is to be missing. It then sets aside a portion of the capacity in the schedule specifically for these repairs. Think of it like a budget where you reserve a small amount of money for unexpected expenses; if a job is duplicated, the algorithm uses the reserved capacity to shift the extra time to a job that needs it. The researchers proved that by managing these reservations and the flow of these repairs, they could recover enough value to ensure the final schedule is extremely close to the best possible one. They also developed a method to group the time blocks in a way that minimizes the chance of conflicts, using a technique that separates the timeline into manageable sections to prevent the repair process from becoming too complicated.

The result of this intricate process is an algorithm that runs efficiently even for very large sets of jobs. It does not require the machines to be faster or the deadlines to be looser; it simply finds a better way to organize the existing constraints. The team demonstrated that their method can achieve a schedule with an expected size of at least eleven-twelfths of the optimal solution, improving upon the previous best guarantees of 4/3 and 17/13. This means that for every twelve jobs that could theoretically be scheduled, their algorithm is guaranteed to find a way to schedule at least eleven. The proof is rigorous and holds for any number of identical machines, regardless of how the jobs are distributed in time. By refining the way these probabilistic models are converted into real schedules, the researchers have shown that the limits of what we can achieve in scheduling are higher than previously thought, offering a more efficient path for organizing complex streams of work in computing systems.

A scientific accuracy reviewer checked the draft against the paper and flagged these problems:

  • Claims previous best guarantee was 'roughly three-quarters' (0.75), contradicting the paper's stated 4/3 (approx 0.75) and 17/13 (approx 0.76) factors which are >0.75. (the paper says: "This improves the recent (4/3 + ε)-approximation... and the (17/13 + ε)-approximation")

Produce a corrected version of the draft. Fix ONLY what the reviewer flagged (verify each point against the paper) and keep everything else — the register, the structure, the wording — unchanged. Output ONLY the corrected explanation.

Drowning in papers in your field?

Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.

Try Digest →