WorksComputer Science
A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization
Abstract
We study unweighted nonpreemptive throughput maximization on an arbitrary number of identical machines: each job has a processing time and a release–deadline window, and the goal is to schedule as many jobs as possible. For every fixed , we give a randomized -approximation. This improves the recent -approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the -approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time , where is the input length.
Introduction
A job with a release time and a deadline may have many possible execution intervals, but it contributes only once to a schedule. This distinction is central to throughput maximization. A fractional solution may place a job in several parts of the time horizon. Sampling these placements independently can produce repeated copies of that job while leaving another job absent. The resulting execution slots still have value: a spare copy can sometimes be replaced by a missing job. The difficulty is to recover this value while respecting both slot capacities and the requirement that each job count once.
We consider the offline, unweighted problem on identical machines, where is part of the input. The input also contains a set of jobs. Job has an integral processing time , release time , and deadline . A feasible schedule selects jobs and assigns each selected job to one machine and one execution interval of length contained in ; intervals assigned to the same machine are pairwise disjoint. The objective is the number of selected jobs. Write OPT for the optimum and for the total binary encoding length. Processing times and window lengths are unrestricted, and no resource augmentation is allowed.
The block-configuration approach of Armbruster, Grandoni, Tinguely, and Wiese [1], building on Chuzhoy, Ostrovsky, and Rabani [2], supplies our starting relaxation. After a small loss, the analysis may restrict attention to a schedule whose executions lie inside blocks, each containing a bounded number of jobs. Sampling a feasible configuration per block produces disjoint execution slots. A maximum matching then assigns compatible jobs to those slots, allowing a slot to serve a job other than the one that generated it. Tong and Xu [8] strengthen this approach through crossing exchanges and coordinated boundary choices. We improve the polynomial-time approximation guarantee for an arbitrary number of identical machines.
Result and comparison
An approximation factor means expected cardinality at least .
Theorem 1.1. For every fixed , there is a randomized algorithm for unweighted nonpreemptive throughput maximization on an arbitrary number of identical machines with binary-encoded integral input data that runs in time and always returns a feasible schedule whose expected cardinality is at least .
Feasibility holds for every outcome of the algorithm. The expectation concerns only the number of scheduled jobs. In particular, the running time is polynomial in the binary input length for every fixed accuracy, uniformly over the number of machines. We develop the proof for one machine in § 2 to § 5. Appendix § 8 extends the construction to every bounded number of machines and combines it with the large-machine algorithm of Im, Li, and Moseley [4].
Table 1. Recent polynomial-time guarantees for unweighted nonpreemptive throughput maximization with arbitrary processing times. All listed factors are in expectation, without resource augmentation. For fixed , the running times are .
In pseudopolynomial time , where is the numerical time horizon, Armbruster et al. [1] obtain a factor and Tong and Xu [8] obtain , both for an arbitrary number of identical machines. Our algorithm enumerates a relaxation of constant order depending on . Writing , Proposition 5.1 gives the explicit implementation bound .
The tradeoff behind the improvement
The block construction distinguishes a nonlocal job’s two boundary blocks, which contain its release and deadline endpoints, from its eligible interior placements. An interior placement belongs to a superblock entirely contained in the job’s window. A local job is eligible in only one block. The relaxation records the distribution of the feasible configuration in each block. It also records joint distributions on every set of at most blocks, where depends only on the accuracy. Each table assigns probability only to tuples of configurations with no repeated job identity. All tables agree with the single-block distributions.
A sampling scheme partitions the blocks into small, disjoint groups. We sample a tuple from each group’s table, independently between groups. A job can appear at most once inside a group. A nonlocal job can therefore appear in both of its boundary blocks only if those blocks belong to different groups. If two jobs have strictly interleaving boundary pairs, the shorter job fits the other job’s intervening boundary slot. This creates a possible repair: a missing job can use the spare boundary slot of a duplicated job.
There are two coupled obstructions to exploiting these repairs. Many missing jobs may want the same spare slot, and the interior recovery may already use part of a missing job’s capacity. We address the first obstruction with a capacitated flow on crossing pairs of active jobs, whose duplication probabilities are at least a small threshold. We address the second by reserving separate fractions of each missing job’s unit capacity for interior assignments and boundary repairs. If are the boundary marginals, is the probability of duplication, is its interior mass, and is the probability of boundary absence, the reservations are and when . They fit together because implies . A bounded-group variance estimate controls the mass lost when the proposed assignments exceed a reservation or a spare slot. This yields a feasible fractional matching; the algorithm obtains at least its value by maximum integral matching.
Now write for retained fractional mass, for expected boundary duplication, and for the repair-flow value of scheme . Up to accuracy losses, its expected matching value is at least
A large flow thus improves the current output. A small flow is useful for a different reason. A residual cut identifies boundary edges that have few crossings among themselves; the active edges left unprotected have total duplicate mass at most the flow value, while inactive jobs contribute only an accuracy loss. A component-preserving separator places the protected endpoints into new bounded-size groups, losing little fractional mass. Sampling these groups prevents their boundary duplicates. The resulting tradeoff is
where is the initial relaxation value and is an internal accuracy parameter. The same quantity rewards the current scheme and bounds the next scheme’s remaining duplication.
An accounting example. Ignore the accuracy losses and normalize to 12 units. The initial duplication bound is . After two coordination steps, and . Set for the final scheme. The three scores are then bounded below by
These three lower bounds sum to 33, regardless of the two flow values. Hence at least one score is at least 11, giving the retained fraction 11/12. For example, and make all three displayed lower bounds equal to 11. This idealized example illustrates the accounting identities. The formal proof restores the accuracy losses, computes the three scores deterministically, and samples a scheme of maximum score.
The structural reason for taking two steps is separate from this algebra. The separator accommodates two protected boundary graphs drawn on opposite sides of the cyclic block order. A third graph would require a new structural argument.
Relation to previous techniques
Tong and Xu [8 Sections 2–3] coordinate noncrossing boundary edges by gluing three-block distributions along a triangulation, using agreement on shared pairs. Their conclusion explicitly proposes both larger crossing exchanges and coordination of crossing graphs admitting bounded-size tree-decomposition bags [8 Section 5]. Thus crossing-family coordination is an existing research direction. Our specific contribution is a flow/residual-cut dichotomy, compatible interior and repair capacity reservations, and a two-page separator that preserves earlier groups. These ingredients implement two rounds of coordination with a quantitative loss bound. We sample disjoint groups from larger tables that agree only on single-block marginals. Each regrouping defines a fresh sampling scheme.
The structural preprocessing follows the block framework of [1]. Its nested-scale density refinement also follows [8 Appendix A], with scale growth chosen here to accommodate the larger table order. Our separator uses the planar separator theorem of Lipton and Tarjan [6]. The additional requirement is to discard entire earlier components so that new groups preserve all surviving earlier coordination.
For historical context, Chuzhoy, Ostrovsky, and Rabani [2] obtained a factor arbitrarily close to for job interval selection, whose formulation permits explicit intervals or intervals specified by job parameters. Im, Li, and Moseley [4] obtained a retained fraction for a constant . Under a different restriction, Hyatt-Denesik, Rahgoshay, and Salavatipour [HDRS20] give a randomized approximation scheme when both the number of machines and the number of distinct processing times are fixed. Our theorem allows arbitrary numbers of machines and distinct processing times.
Organization. § 2 defines the relaxation and its parameters. § 3 proves the flow-to-coordination tradeoff, and § 4 checks the three matching-capacity accounts. § 5 combines the guarantees and bounds the running time. Sections A and B contain the structural proofs. Section C gives the extension to an arbitrary number of identical machines.
Model and a local relaxation
We first consider one machine. Appendix § 8 extends the result to an arbitrary number of identical machines. A job has an integral release time , deadline , and positive integral processing time . Its window is . A schedule assigns each selected job one half-open execution interval of length contained in its window; execution intervals must be disjoint. All numbers are given in binary. We write for the number of jobs, for the input encoding length, and OPT for the maximum number of scheduled jobs. Delete jobs with , and solve instances with at most one job directly. A common translation of all times lets us assume . Put .
| Notation | Meaning |
| , | Loss parameter and integer number of portions or scales. |
| , | Jobs per block; maximum number of blocks in a local table. |
| , | Group-size bound at step ; jobs in one sampled group. |
| , | Original LP value; retained placement mass at step . |
| , , | Retained release, deadline, and interior marginals of nonlocal job . |
| , | Probabilities of two boundary copies and no boundary copy. |
| , | Total duplication probability and maximum repair flow at step . |
| , | Active jobs and the unprotected jobs identified by the residual cut. |
| , | Indicators of no boundary copy and two boundary copies. |
| , | Total retained interior mass and the algorithm’s output job set. |
| , , | Activity threshold, middle-arc capacity, and crossing-degree bound. |
| , | Refinement base and nested retained job sets in Appendix § 6. |
Table 2. Principal notation. The per-job quantities , , , , and indicators , refer only to nonlocal jobs. All job marginals and probabilities refer to the current grouping; step indices are added when several groupings are compared. The definitions in the text specify the degenerate cases.
Fix an integer and put . The same integer will count the mass portions in rounding and the grouping scales in preprocessing. A block partition divides into consecutive half-open intervals. A superblock partition groups consecutive blocks. The release block of contains ; its deadline block is the unique block with . A job is local if these blocks agree. A local job is eligible only in that block. A nonlocal job is eligible in its two boundary blocks and in any other block whose entire superblock is contained in its window. The latter occurrences are called interior. An eligible schedule executes each job in one eligible block.
Lemma 2.1 (Preprocessing). For any computable integer-valued function depending only on and , a deterministic algorithm either solves the instance exactly or constructs candidate block–superblock partitions , each with its own cap depending only on and . For at least one candidate , writing , , and , there is an eligible schedule that crosses no block boundary, uses at most jobs per block, and satisfies
The algorithm runs in time, where the hidden constant may depend on the prescribed function .
The proof, including the dependence on , appears in Appendix § 6. The schedule in the conclusion is an analysis witness; the preprocessing algorithm computes the candidate partitions. The table-order function used by our algorithm is specified in (9) below.
For a fixed candidate , write for its partitions and abbreviate and . Let consist of all eligible job sets of size at most schedulable inside block . Store one feasible execution schedule for each set, including the empty set. To construct this family, enumerate job sets and orders and schedule each order at its earliest possible start times inside . An order is feasible if and only if this procedure completes every job by its deadline and completes all jobs by the right endpoint of . Thus the family can be constructed in time per block. For nonempty of size at most , let consist of tuples with and with no job identity appearing twice.
The relaxation has a probability distribution on and a distribution on for every such . It imposes
and maximizes . Every distribution is nonnegative and normalized. The consistency constraints equate only the single-block marginals in (2).
Every candidate has blocks, as follows from the construction in Appendix § 6. Consequently the explicit LP has variables and constraints. An eligible schedule with cap induces a feasible integral point, using the restriction of that schedule in every table. Solve each candidate’s LP with its own parameters and , obtaining value . Discard candidate if or , and choose a remaining candidate with largest value. From now on denote the selected partitions, parameters, and LP value. Lemma 2.1 ensures that at least one candidate survives and that the selected solution satisfies
From this point onward, denotes this fixed original LP value.
Coordinating the boundary blocks
A grouping partitions a subset of the original blocks into sets of size at most . Deleted blocks are not sampled. Independently for each , sample a tuple from and use the stored execution intervals of its configurations as candidate slots. The matching step will choose the jobs actually executed. Groups need not be consecutive. Put ; any sampled group contains at most distinct jobs. Write for the sum of retained placement marginals.
For a nonlocal job , let be its marginals in its retained release and deadline blocks, respectively, taking a marginal to be zero if the corresponding block was deleted. Let be its total retained interior mass. Define
The table for a group never repeats a job; different groups are sampled independently. Hence is the probability that both boundaries contain , and is the probability that neither does. In particular,
The first inequality is equivalent to . For the second, , since . All sums over boundary pairs below are over nonlocal jobs.
Set and . Let be the set of active jobs. Two boundary pairs cross when their four blocks strictly interleave in chronological order. Orient a crossing if , with any fixed tie-breaking order on job identities. One boundary block of lies strictly between the two boundary blocks of , and is therefore entirely contained in . The execution slot of in that block can accommodate . A crossing is permitted if both jobs are active and the four boundary blocks belong to four distinct groups. See Figure 1.
Figure 1. One of the two strictly interleaving orders. The whole block lies in the window of . A slot generated by in this block can therefore serve when . The opposite interleaving order uses . The drawing is schematic.
The flow below measures repairs available to the current grouping. A large flow improves its matching guarantee; a small flow allows the residual-cut and separator construction to reduce duplication in the next grouping. Comparing three groupings uses this tradeoff twice, before any sampling.
Build a directed network with source , sink , left and right copies of each active job, arcs and of capacity , and an arc of capacity for each permitted crossing . Let be a maximum flow on the middle arcs and its value. In particular,
Let and be the sets of reachable left and right copies, respectively, in the residual graph from . Define
Protect every job in . On the retained block vertices draw its boundary pair as a chord, merging parallel chords. Call the resulting simple graph the protected graph.
We use the following separator statement, proved in Appendix § 7. For two simple graphs on the same cyclically ordered vertices, each with at most crossings per edge, suppose the first graph has components of size at most . For any integer , we can delete whole components of the first graph, containing at most
so that every remaining component of their union has size at most . Crossings here refer to chords with strictly interleaved endpoints; edges sharing an endpoint do not cross.
Define the constants
They are integers because is an integer. This is the function used in preprocessing and in the LP.
Initially every block is a singleton group, and the old graph is edgeless. At step , compute the network and protected graph for the current grouping. Apply (8) to the old graph and protected graph with , , and . Delete the whole old components returned by the procedure and group the remaining blocks by connected components of the union. The first resulting old graph is the retained protected graph. After the second step no further old graph is needed. Write , , for the retained mass, duplication mass, and maximum flow at step , and put .
Lemma 3.1 (Coordination). Each of the two steps is well-defined and satisfies
Proof. Fix one of the two steps and its current grouping. We first bound the mass that cannot be protected, then establish the separator hypotheses, and finally track the retained marginals after regrouping.
The residual cut charges unprotected mass to the flow. The sink is not reachable from in the residual network of a maximum flow. If , then has no positive residual capacity; otherwise that arc would make reachable. Its flow is therefore . Similarly, implies that is saturated, since a positive residual capacity would make reachable.
These two saturation statements alone would allow a factor-two bound. The following disjointness avoids that loss. If and , then : positive flow would create the reverse residual arc , making reachable. Consequently,
count disjoint sets of positive middle-arc flows. A job in both defining classes of is counted twice on the left below, which only increases the bound. Thus
This is the source of the large-flow/small-duplication tradeoff: protecting all other active pairs leaves at most active duplicate mass unpaid.
Protected edges have bounded crossing degree. For protected jobs , a permitted arc goes from a reachable vertex to an unreachable one. It must be saturated, so . The total flow incident to the left and right copies of one job is at most . There are therefore at most permitted crossing arcs incident to a fixed protected job.
If two protected pairs cross but the crossing is not permitted, their boundary blocks use fewer than four groups. Each pair individually uses two distinct groups because it is active. Hence the other pair has a boundary in one of the fixed pair’s two groups. Activity gives : their product is at least , and neither factor exceeds one. A group has expected total placement count at most . At most active jobs can consequently have a boundary in any one group. The nonpermitted crossings of the fixed pair number at most . Combining the two cases yields
For a simple protected edge, fix any job represented by that edge and apply the preceding count. Every distinct crossing simple edge has a represented crossing job, so merging parallel edges cannot increase the bound.
The separator applies at both steps. Initially the old graph has no edges. After the first step, it is a restriction of the first protected graph, and its connected components are the groups of size at most . Its crossing degree is at most . The second protected graph has crossing degree at most by the preceding argument. These are exactly the two applications for which the hypotheses of Lemma B.2 have been established.
At step , the separator removes at most blocks; we used the original number of blocks to upper-bound the current number. Each block has placement mass at most , since every one of its configurations has at most jobs. The choice of gives
This proves the retained-mass inequality.
Regrouping eliminates the protected duplicates. Both endpoints of every surviving protected edge lie in one new connected component. Its job cannot be duplicated when that component is sampled from its table. If either endpoint was deleted, its new duplication probability is also zero. A pair already internal to an old group remains internal or loses both endpoints, because we delete whole old groups and never split a surviving one.
For any other pair, retaining both endpoints preserves its two individual marginals. Merging its groups changes its duplication probability from to zero; deleting an endpoint also changes it to zero. Thus no pair’s duplication probability increases. Active unprotected pairs contribute at most by (11). For an inactive pair, and , including the case . Hence . Summing over those pairs gives at most . This proves the duplicate-mass inequality. □
The two-step graph invariant
The two coordination steps use the following graph invariant. After one step, the old graph is a single protected chord family with bounded crossing degree. The second step places that family and the new protected family on the two hemispheres used in Lemma B.2. After this step, the old graph would be their union. The established crossing bounds apply separately to its two families. A further application of the separator would require a crossing bound for their union in the fixed cyclic order.
This distinction persists even when all old components are tiny. For any , put vertices in cyclic order
The family consisting of and the family consisting of the nested edges are each crossing-free. Their union is a matching, so each component has two vertices, but crosses all edges of the other family. Thus neither pagewise crossing bounds nor a bound on old-component size supplies the one-page hypothesis needed for another invocation of our lemma. The example isolates the failure of this structural implication.
To separate the algebraic opportunity from this missing structural step, suppose hypothetically that one could carry out steps with the same bounds as Lemma 3.1, and apply Lemma 4.1 to all groupings. Put . The same calculation would give
Here and explain every term in the second line. Under these hypotheses, extending the structural argument to more rounds would therefore improve the approximation ratio.

Figure 2. Why the established pagewise bounds do not automatically apply to the accumulated old graph. In the order , the two matchings and are each crossing-free. Their union has only two-vertex components, but crosses all other edges in a common one-page drawing. The case is shown. This is a counterexample to an inference from pagewise crossing bounds and component size alone.
Matching sampled slots
For any grouping, treat every sampled execution as a slot . A job is compatible with the slot if
Compute a maximum bipartite matching between all jobs and all slots. An assigned job starts at . Since the slots are disjoint and matching uses each job and slot at most once, this is a feasible schedule. The fractional matching used next is only an analysis certificate.
Lemma 4.1 (Rounding). For any grouping with group size at most , and any nonnegative weights on permitted crossings satisfying (7), the expected maximum matching cardinality is at least
A variance bound
The following fact allows arbitrary correlations inside one sampled group.
Lemma 4.2. Suppose independent random group samples each contain at most job occurrences, with no repeated identity. The occurrence record of a job in a group specifies the block containing it,
or records its absence. For each job , let be determined only by its occurrence records in a fixed set of at most two groups. If , then
Proof. Write . If , couple the conditional experiments given and by using identical samples for all groups outside the at most two determining groups. Independence makes this coupling valid: these outside groups retain their original joint law under either condition. The two samples in the determining groups contain altogether at most job identities. A flag can change only if its job is among these identities, including the case where the job appears in both samples but in different blocks. Therefore the coupled values of differ in absolute value by at most , and
If is constant, its covariance is zero. Finally sum these inequalities with weights , using .
Constructing the fractional matching
Proof of Lemma 4.1. Let and indicate boundary absence and boundary duplication. Then and . The baseline counts each sampled local job and each boundary-present nonlocal job exactly once. Writing , its expected size is . Its actual assignment to boundary slots will be completed after repairs. For each absent nonlocal job reserve capacity for interior assignments and for boundary repairs. Their sum is at most one by (6). Whenever , both numerators are zero; such terms are defined to be zero. Table 3 records the capacities that will be checked jointly after the two kinds of assignment have been constructed. § 4.3 illustrates these reservations on a concrete feasible set of local tables.
| Account | Assigned mass | Capacity check |
| Absent recipient | Interior at most ; repairs at most | Sum at most , since . |
| Duplicated donor | Repairs export at most in total from its two boundary slots | If , two unit slots retain at least one unit for . Each slot exports at most one. |
| Other baseline jobs | One unit for each sampled local job or job with exactly one boundary copy | Its own sampled slot supplies that unit. |
| Interior slots | Used only for absent recipients | The portion assignment uses at most one unit per slot. |
Table 3. The simultaneous capacity accounts in the fractional-matching certificate. An absent job cannot also be a donor or a boundary-present baseline job. Ratios are used only when their denominator is positive; a zero-probability event contributes no assignment.
Interior assignments. Fix a superblock with total interior mass . Let be the retained interior mass of in this superblock. Sort these masses by nonincreasing processing time, breaking ties arbitrarily, and split the resulting mass interval into consecutive portions, each of mass . A job’s mass may straddle a cut. Let be its mass in portion . Define the demand
For every sampled interior slot generated by in this superblock, allocate the fraction to supply for portion ; let the resulting total supply be . Terms with are absent. The fractions over all portions sum to one for every such slot. Both and have expectation , by the preserved one-block marginals. Each demand coefficient is at most one, so Lemma 4.2 gives . Write as a sum of independent group contributions in . For a variable , , hence .
For , every demanded job in portion has processing time at most the length of every slot supplying portion . Every demanded job’s window contains the entire superblock. Thus the corresponding fractional bipartite graph is complete, and it can carry a flow of value . The following estimate holds for arbitrary dependence between demand and supply:
Summing and using gives an expected contribution of at least . A zero-mass superblock needs no assignment and satisfies the same lower bound. Summing over superblocks, and using and (4), the expected interior contribution is at least
Each supply portion is used at most once. The total demand assigned to job over all superblocks is at most , so all interior assignments respect the reserved capacities.
Boundary repairs. For each positive-weight permitted pair propose a transfer
Positive weights imply and . The four determining groups are distinct, so and are independent and . Let and . Scale any overloaded row down to capacity , and then scale any overloaded column down to capacity . Column scaling cannot increase a row sum. The total removed mass is at most the sum of the original row and column excesses.
Put and . Conditional on , every flag in row depends only on groups outside ’s two boundary groups. Its joint distribution with the other row flags is consequently unchanged by this conditioning. Applying Lemma 4.2 with weights gives
The same argument for a column, conditioning on and using weights , gives
If , then . Multiplying the conditional bounds by and , respectively, bounds expected row and column losses by and . There are at most active jobs, by (6), and . Cauchy–Schwarz therefore bounds total expected loss by
This also covers , when every transfer is zero.
Checking all capacities simultaneously. Realize each surviving transfer on the donor’s boundary slot lying inside the recipient’s window. The slot is compatible by the crossing geometry and . Fix a duplicated donor . Column scaling bounds the total mass exported from its two slots by one; hence the exported mass on either individual slot is also at most one. If these two exported masses are , their unused capacities satisfy . Assign one unit of across these unused capacities, for example on the first slot and on the second. This is feasible because . The job is boundary-present and therefore receives no interior or repair assignment of its own.
A job with exactly one boundary occurrence receives one unit on that slot and exports nothing, since its duplication flag is zero. A sampled local job also receives one unit on its own slot; it has no boundary-repair or interior role. Thus all baseline jobs receive exactly one unit. The remaining recipients are boundary-absent nonlocal jobs. Their combined interior and repair assignment is at most , and none is a baseline job or a donor. Interior supplies use only sampled interior slots, whose total assigned portion fractions are at most one. Boundary assignments use only boundary slots, and local assignments use only local slots. These three classes of slots are disjoint even when their generating identities coincide. Consequently every job and every slot has total incident assignment at most one: all assignments together form a feasible fractional matching. Its expected value is at least
The bipartite matching polytope is integral [7 Corollary 3.7a], so for each outcome the maximum integral matching has at least the value of this fractional matching.
A small capacity example
The following feasible local-table example illustrates the reservations. Take five blocks , , each forming its own superblock and sampling group, and two jobs
Consider a distribution that places in with probabilities , respectively, and independently places in or , each with probability . Use execution intervals for the three placements of , and for those of . Every outcome is a feasible schedule. Its restrictions therefore define feasible local tables of any order.
Sample the singleton groups independently from these table marginals. For , the boundary and interior masses are and , so
A boundary-absent job can thus receive up to 8/9 of a unit through interior slots and up to 1/9 of a unit through repairs, for a total of at most one unit. For , duplication has probability . Its slot can accommodate , since the boundary pairs and cross and . For the permitted flow weight , the proposed transfer on the event is . This is at most , since , and so neither row nor column scaling is needed in this example. Its expectation is exactly . On that event the duplicated keeps one unit in its slot, while the repair uses at most one unit of its slot. This displays explicitly why a donor can preserve its own baseline assignment while an absent recipient combines two separately reserved sources of mass.
The algorithm and its guarantee
Compute the two coordination steps and the three scores for , with . Choose a grouping with maximum score, sample its groups independently from their local tables, and return a maximum compatible job–slot matching. Let be the set of jobs in this matching. Only the selected grouping is sampled.
Proof of Theorem 1.1 for one machine. If preprocessing solves the instance exactly, there is nothing to prove. Otherwise and . Lemma 3.1 gives
By Lemma 4.1, choosing a grouping with maximum score yields
For the last inequality, the coefficient of is positive and (4) applies; expanding the product loses at most .
It remains to account for finite random bits and binary arithmetic. Set and . All caps, refinement depths, group sizes, and table orders are constants depending only on . Greedy earliest-completion computations and feasibility checks use addition, maximum, and comparison of binary endpoints. Their intermediate numbers have encoding length polynomial in and ; no algorithm enumerates the numerical time horizon. The explicit rational LP has polynomial size for fixed , and a polynomial-time rational LP algorithm produces an optimal solution of polynomial encoding length [5 Section 6]. All subsequent marginals, capacities, scores, maximum flows, graph separators, and maximum matchings have polynomial encoding size and can be computed in polynomial time in this explicit representation; for maximum flow and matching, see [7 Chapters 3–4].
For completeness, suppose the selected grouping requires independent draws and each table has support at most . Put . Round each table probability down to a multiple of and assign the remaining probability to one outcome that originally had positive probability. The resulting distribution has total-variation distance at most from the original distribution. The product distributions have distance at most , by coupling the draws independently. Output cardinality lies in , so expected cardinality falls by at most . Sampling each rounded table uses exactly random bits and preserves feasibility. If there no retained groups, no draw is required; the score bound already handles this case. Because the nonempty instance has , the implemented algorithm retains at least in expectation. Finally,
The algorithm therefore has the claimed approximation factor and running time .
Dependence on the accuracy parameter
We bound the running time of the explicit enumeration above, including the nested scales in Appendix § 6.
Proposition 5.1. With the least-multiple choice of grouping scales in the preprocessing construction and , the one-machine algorithm can be implemented in
time for . Instances with at most one job are solved directly. The same bound holds for an arbitrary number of identical machines.
Proof. We prove the one-machine bound here; Section C.3 establishes the same bound for arbitrary . Keep and define the absolute constant . The parameter definitions in (9) give and . Hence
and, since and ,
The preprocessing cap is , so . Write and . The least multiple of above a real threshold is at most . In the scale recurrence the threshold dominates . Applying (15) therefore yields
Iterating for steps gives the explicit estimate
It follows that all candidate caps , table orders , and the exact-enumeration cutoff are at most . Enumerating all ordered job subsets up to the cutoff costs times a polynomial in the binary input length. The local relaxation has entries and constraints, and all remaining computations are polynomial in this explicit representation and . There are only candidates. Parameter construction and factors depending only on can also be absorbed into the displayed bound for . Thus the total time is . Finally the choice in the theorem proof has .
Proof of the preprocessing lemma
We prove Lemma 2.1. The construction first produces fine blocks with a constant schedule cap, and then uses nested grouping scales to accommodate the prescribed function .
Greedy refinement
For an interval and a supplied set of job identities , write for the following subroutine. Make a fresh working copy of . Repeatedly select from that copy a job with earliest feasible completion in , starting no earlier than the preceding completion, and remove the selected identity from this working copy. Stop when no job in the copy can be appended. The supplied set is never modified by the subroutine. All ties are broken deterministically. The following charging observation will be used for jobs that remain unselected throughout a run. If is a feasible execution of such a job inside the run’s interval, then some greedy completion belongs to . Indeed, just after the last greedy completion at or before , or at the left endpoint if none exists, that execution is an available candidate. Thus either the next greedy completion is at most , contradicting its choice as the last one, or it lies in . If there is no next selection, the available candidate contradicts termination. Disjoint executions have disjoint intervals , so charging each execution in this way defines an injection into the greedy completions.
Put , , and . Run , and let be its selected identity set; retain the resulting execution intervals as well. Cut after every selected jobs, except after the final selected job. For every iteration , carry out the following scan.
Reset the iteration’s availability set to and initialize . No removal from a previous iteration is carried over: its selected identities are precisely the new input set.
Visit the blocks present at the start of iteration , from left to right. For a parent block , compute the tentative schedule . Its construction modifies only the subroutine’s fresh working copy.
If , keep its execution intervals, add its identities to , and replace by . Subdivide after every selected jobs, except after the final selected job. The resulting children are not scanned again at this iteration.
If , discard the tentative schedule and leave unchanged. In particular, its selected identities can be tried in later parent blocks of this same iteration.
Here and below, a schedule in a set operation denotes its identity set. The kept parent schedules are disjoint in time. Their identities are also disjoint, because a committed identity is removed from before the next parent run. Their union is therefore a feasible schedule on the identity set . Every identity considered during iteration belongs to , proving . Stop at the first iteration with . Such an iteration exists by : otherwise the disjoint differences for would contain more than jobs.
Let and for . In any schedule lying within a block after iteration , at most jobs belong to . For , all these jobs were unselected, and the charging observation bounds their count by the at most greedy completions in the block. For , each identity in belongs to the reset set and to no schedule committed in iteration . It is consequently present in at the start of every parent run. A tentative selection can remove it from that run’s working copy, but discarding the run leaves the iteration-level set unchanged. In a kept child, all jobs were unselected in that parent’s run, and charge to at most completions in that child. In an unkept parent, at most jobs are identities of its tentative schedule; all remaining jobs charge to at most completions. The bound also holds in all finer blocks produced later. The number of cuts created throughout the construction is at most
Take an optimal schedule and remove every execution that crosses a final cut. At most one execution crosses each cut, so this loses at most jobs. Let be the stopping iteration. Remove from this aligned schedule all identities in , clear all kept parents of iteration , and insert in those parents. Removing and inserting has net loss at most . After removing , the remaining identities belong to . Every kept parent therefore contains at most
of them. Each kept parent contributes more than jobs to ; there are at most kept parents. Clearing them loses at most more jobs. The resulting aligned schedule consequently satisfies
Each kept child contains only its inserted jobs, at most of them. An unkept parent contains at most remaining jobs. Thus every final block has at most jobs of . Denote this fine partition by and its size by . If , the cut bound gives
The number of cuts is also , since every has at most jobs and is a constant.
Nested grouping scales
Recall that and set . Recursively choose to be the least positive multiple of satisfying
All these numbers depend only on and the prescribed function . Let . Enumerate all subsets and orders through size , using earliest-start feasibility tests. If no feasible schedule of size exists, these tests return an exact optimum, since any larger schedule would contain such a subset. Otherwise and the preceding construction gives
For candidate , form blocks from consecutive batches of fine blocks and superblocks from batches of fine blocks, truncating the final batches. Divisibility ensures the partitions are nested. Every block contains at most jobs of , and the numbers of blocks and superblocks are at most and , respectively.
Fix an execution of a job in . If it is ineligible at level , its block is neither boundary block and so lies entirely in its window, whereas its superblock does not. At every finer level, the superblock containing this execution is contained in the level- block, hence inside the window; the execution is eligible. At every coarser level, the block containing the execution contains its level- superblock. Because that superblock contains the execution but is not contained in the window, it contains a release or deadline endpoint in precisely the half-open endpoint convention defining the boundary blocks. The coarser block is therefore a boundary block, and the execution is eligible there as well. Thus an execution violates eligibility at most one level.
Averaging over the candidates gives a level for which deletion of all ineligible executions loses at most . Its remaining schedule satisfies . Furthermore (17) gives
Since , the chosen level satisfies
Output all candidates; the schedules and were used only for the analysis. The enumeration has constant maximum subset size, and every greedy pass uses binary arithmetic on input endpoints and processing times. This proves both the running-time bound and all claims of Lemma 2.1.
Separation of two boundary graphs
We use the planar separator theorem of Lipton and Tarjan [6] in its unweighted form: an -vertex planar graph has a vertex separator of size at most whose deletion leaves components of size at most . Such a separator is computable in polynomial time. We first turn this balanced separator into a bound on all remaining components. We then transfer that bound from a planarization back to the block vertices, while deleting complete old groups. The constants below leave slack in the later loss budget.
Lemma B.1 (Recursive planar separation). Let be a planar graph on vertices and let be an integer. In polynomial time one can find a set with
such that every component of has at most vertices.
Proof. First consider a connected planar graph on vertices. Apply the planar separator theorem once. If a remaining component has more than vertices, it is unique; its size is at most . Apply the theorem again to that component. Every component resulting from the second application has at most vertices. Thus the union of the two separators is a half-balanced separator, and its size is at most
If no second application is needed, the same bound holds.
Apply this half-balanced separation recursively to every component with more than vertices. Charge the deletion of at most vertices from a processed -vertex component evenly to its vertices, at rate . For a fixed original vertex, the processed components containing it form a chain; the size of each child is at most half its parent’s size. Reading the chain backward from its last component, whose size exceeds , we bound the total charge to the fixed vertex by
Summing over the original vertices bounds the total number deleted. The recursion has at most nonempty leaves and polynomially many calls. Applying the construction independently to the initial components handles disconnected graphs.
Two edges with four distinct endpoints in a cyclic order cross if their endpoints strictly alternate. Edges sharing an endpoint do not cross. For an integer , put
Lemma B.2 (Two-page separation). Let , , and be integers, and let be simple graphs on the same cyclically ordered vertices. Suppose that, within each graph, every edge crosses at most other edges. Suppose also that every connected component of has at most vertices. For every integer , one can delete a union of whole -components, containing at most
vertices, so that every remaining component of has at most vertices. The construction takes polynomial time.
Proof. A planar representation of the two families. Draw and on opposite hemispheres of a sphere, placing their common vertices on the equator in the prescribed cyclic order. On each hemisphere use a chord drawing; a sufficiently small perturbation makes all crossings pairwise, without changing which pairs of edges cross. Intersections between edges from different graphs occur only at their common endpoints on the equator.
For either graph, form the graph whose vertices are its edges and whose adjacencies are crossings. Its maximum degree is at most , so a greedy coloring uses at most colors. Edges of one color give a simple outerplanar graph on the original vertices, with at most edges. Consequently each hemisphere has at most edges and at most crossings. The planarization , obtained by introducing one vertex per crossing, has at most vertices. Parallel edges in may be suppressed, since they do not change its vertex separators or its connected components.
Deleting whole old components. Apply Lemma B.1 to . Replace every deleted crossing vertex by the endpoints of the two original edges passing through that crossing; retain every deleted original vertex. The resulting set of original vertices has size at most four times the planar separator’s size. Delete all -components meeting this set. Since each such component has at most vertices, the number of original vertices deleted is at most .
Why the surviving union is small. For every surviving original edge, its subdivided path in avoids the planar separator: otherwise either an endpoint or all endpoints of an edge through a deleted crossing would have been removed. Every connected component of the surviving union therefore maps into one component of the separated planarization. Such a component contains at most planar vertices, and hence at most original vertices. This proves the required bound. The drawings, crossing enumeration, planarization, separator recursion, and component deletions all have polynomial size and can be constructed in polynomial time.
An arbitrary number of identical machines
Let be the number of machines and the optimum. We use a common time partition for all machines. For bounded , each block configuration records a feasible schedule on all machines, and each sampled slot retains its machine label. For sufficiently large , the algorithm of Im, Li, and Moseley [4] gives the required guarantee. This bounded/large-machine division is also used by Armbruster et al. [1 Section 4].
Preprocessing for a bounded number of machines
Fix a positive integer . We extend Lemma 2.1 to identical machines, with a cap on the total number of jobs in a block across all machines. Its constants may depend on . The block–superblock partition is common to all machines. Write for the optimum on machines.
Lemma C.1. For every fixed positive integer and every prescribed computable integer-valued function depending only on and , a deterministic algorithm either solves the -machine instance exactly or constructs candidate block–superblock partitions, with caps depending only on , , and . At least one candidate admits an eligible -machine schedule with at most its cap jobs per block and
The algorithm runs in time, where the hidden constant may depend on .
Proof. Run the greedy refinement of Appendix § 6 with
Each invocation of still constructs a one-machine schedule, with the same fresh working copy of and the same iteration-level reset and commitment rules. Thus the sets remain nested, each has a feasible one-machine schedule, and the stopping iteration is at most .
The charging observation in that appendix now has multiplicity at most . Indeed, restrict an -machine schedule of identities unselected by a greedy run to one machine. Its execution intervals are disjoint, so their charges to greedy completions are injective. Summing over the machines gives the claim. Consequently, inside any block after iteration , at most scheduled identities belong to . In a kept child, all these identities were unselected and charge to at most completions with multiplicity at most . In an unkept parent, at most identities belong to its tentative greedy schedule; all other identities charge to its at most completions. This gives . The same bounds persist in finer blocks.
The number of cuts is at most
Deleting every optimal execution that crosses a cut loses at most jobs, because at most one execution on each machine crosses a cut. Let be the stopping iteration. Remove all identities in , clear all machines inside every kept parent of iteration , and insert its one-machine greedy schedule on the first machine. The deletion of and insertion of have net loss at most . After deleting , each kept parent contains at most
remaining jobs. There are at most kept parents, so clearing them loses at most jobs. The resulting aligned schedule satisfies
Every kept child contains at most inserted jobs, and every unkept parent contains at most remaining jobs. Thus the cap is . If , the number of fine blocks satisfies . The construction has blocks and uses binary arithmetic on the original endpoints.
Apply the nested grouping scales from Appendix § 6 with this value of and the same . To handle the small-optimum branch, let and enumerate job subsets of size at most , assignments to machines, and orders on each machine. For each such choice, earliest-start schedules test feasibility using binary arithmetic. If no feasible subset of size exists, this enumeration finds an optimum. Otherwise the lower bound on and the nested-scale eligibility argument apply unchanged: eligibility depends on the job’s window and execution interval. In particular, each execution is ineligible at at most one of the levels. A good level has an eligible -machine schedule with
Here bounds the total number of jobs per block. The last two inequalities follow from the same calculation as in the single-machine case, since . For fixed the running time is .
Configurations and rounding on a fixed number of machines
Fix a constant number of identical machines and apply the preprocessing construction above. The resulting blocks form a common partition of the time horizon for all machines. The cap bounds the total number of jobs in a block, summed over the machines.
For each block , let contain the eligible job sets of size at most that admit a schedule on the machines inside . Store one such schedule for each set, including the machine assigned to each job. These configurations can be enumerated by assigning each candidate job to one of the machines and enumerating the order on each machine. For a fixed assignment and orders, schedule each machine’s jobs successively at their earliest feasible start times in . The test succeeds for some assignment and orders exactly when the set is feasible. Since and are constants, this takes time per block.
The distributions and , their consistency constraints, and the job constraints are the same as in § 2. Every tuple in contains each job identity at most once across all its blocks and machines. Restricting the eligible schedule provided by preprocessing to each table gives a feasible integral point. Consequently the candidate-selection rule still yields (4), with .
The boundary blocks of a job depend only on its release time and deadline. In particular, each nonlocal job still has precisely two boundary blocks. Within a sampled block or group its identity occurs at most once. Thus the quantities , , , , and the reservations in (6) have the same interpretation. A group of at most blocks contains at most job occurrences. The bounds on active jobs incident to a group, the protected crossing degree, and the mass lost when blocks are deleted therefore remain unchanged. This proves the two coordination inequalities in (10).
Give every sampled slot its stored machine label. On each machine the slots are pairwise disjoint: this holds within a configuration, and different blocks are disjoint time intervals. A compatible job assigned to a slot runs on that slot’s machine from for time units. The compatibility condition (12) places its execution inside the slot and inside its window. A matching consequently produces a feasible schedule on the machines.
The fractional-matching analysis also applies to these labelled slots. The flags for boundary absence and duplication are determined by the same occurrence records in at most two groups, so the variance bound uses the same . For interior assignments, every recipient window contains the supplying superblock and its processing time fits the supplying slot. For a boundary repair, the crossing relation places the selected donor boundary slot inside the recipient window and $p_j \le p_k ensures that the recipient fits. Identical machines allow either assignment on the machine of the chosen slot. The capacity reservations and the donor’s remaining baseline assignment concern individual jobs and slots, so all capacity calculations in § 4 are unchanged. Hence the expected maximum matching cardinality is at least .
Combining the three scores as in § 5, and using the same finite-bit implementation, gives an expected cardinality of at least . With the choice of made there, this is at least .
An arbitrary number of machines
Im, Li, and Moseley [4] give, for every fixed , a polynomial-time algorithm for unweighted throughput maximization on identical machines whose expected retained fraction is at least
for an absolute constant and , where denotes the natural logarithm. Their unweighted result allows binary-encoded release times, deadlines, and processing times. We use this result for a sufficiently large number of machines, as in the extension of Armbruster et al. [1 Section 4].
Fix and the absolute integer
For , the inequality gives
The algorithm of Im, Li, and Moseley therefore returns a feasible schedule with expected cardinality at least
For , apply the fixed-machine construction in the preceding subsections. This proves the approximation guarantee in Theorem 1.1 for every number of machines.
We may replace an input machine count larger than by , since any schedule of at most jobs uses at most machines. Instances with at most one job are solved directly. For , the preprocessing parameters satisfy
uniformly over this range of . The bound and the recurrence for the nested scales are unchanged. The proof of Proposition 5.1 therefore gives the same bound
The additional factor for machine assignments is absorbed into because and . For , the algorithm invoked at the fixed accuracy runs in polynomial time in the binary input length. The displayed bound consequently holds for the complete algorithm with an arbitrary input machine count.
Acknowledgment
ChatGPT 6 Pro was used to assist in developing the mathematical proofs and preparing the manuscript.
References
- [1]Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese. Improved approximation algorithms for non-preemptive throughput maximization. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC ’26, pages 2083–2093. ACM, 2026. Full version: arXiv:2603.29451v1. doi:10.1145/3798129.3800912.DOI
- [2]Julia Chuzhoy, Rafail Ostrovsky, and Yuval Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research, 31(4):730–738, 2006. doi:10.1287/moor.1060.0218.DOI
- [4]Sungjin Im, Shi Li, and Benjamin Moseley. Breaking 1 − 1/e barrier for nonpreemptive throughput maximization. SIAM Journal on Discrete Mathematics, 34(3):1649–1669, 2020. doi:10.1137/17M1148438.DOI
- [5]Leonid G. Khachiyan. Polynomial algorithms in linear programming. Zhurnal Vychislitel’noĭ Matematiki i Matematicheskoĭ Fiziki, 20(1):51–68, 1980. In Russian; English translation in USSR Computational Mathematics and Mathematical Physics 20(1):53–72. Original article.DOI
- [6]Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177–189, 1979. doi:10.1137/0136016.DOI
- [7]Alexander Schrijver. A course in combinatorial optimization. Course notes. CWI and University of Amsterdam, 2017. Version of March 23, 2017. https://homepages.cwi.nl/~lex/files/dict.pdf.
- [8]Weitian Tong and Yao Xu. Coordinating boundaries: Improved approximation algorithms for unweighted non-preemptive throughput maximization, 2026. Preprint, arXiv:2610.34656v1.arxiv.org/abs/2610.34656
