betaFeedback

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 ε>0\varepsilon>0, we give a randomized (12/11+ε)(12/11+\varepsilon)-approximation. This improves the recent (4/3+ε)(4/3+\varepsilon)-approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the (17/13+ε)(17/13+\varepsilon)-approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time nOε(1)poly⁡(N)n^{O_\varepsilon(1)}\operatorname{poly}(N), where NN 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 MM identical machines, where MM is part of the input. The input also contains a set JJ of nn jobs. Job jj has an integral processing time pj>0p_j > 0, release time rjr_j, and deadline djd_j. A feasible schedule selects jobs and assigns each selected job to one machine and one execution interval of length pjp_j contained in [rj,dj)[r_j,d_j); intervals assigned to the same machine are pairwise disjoint. The objective is the number of selected jobs. Write OPT for the optimum and NN 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 ρ≥1\rho\ge1 means expected cardinality at least OPT/ρ\mathrm{OPT}/\rho.

Theorem 1.1. For every fixed ε>0\varepsilon> 0, 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 nOε(1)poly⁡(N)n^{O_\varepsilon(1)}\operatorname{poly}(N) and always returns a feasible schedule whose expected cardinality is at least OPT/(12/11+ε)\mathrm{OPT}/(12/11+\varepsilon).

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].

ResultIdentical machinesApproximation factor
Armbruster et al. [1]Arbitrary4/3+ε4/3+\varepsilon
Tong–Xu [8]Arbitrary17/13+ε17/13+\varepsilon
Theorem 1.1Arbitrary12/11+ε12/11+\varepsilon

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 ε>0\varepsilon> 0, the running times are nOε(1)poly⁡(N)n^{O_\varepsilon(1)}\operatorname{poly}(N).

In pseudopolynomial time (nT)Oε(1)poly⁡(N)(nT)^{O_{\varepsilon}(1)}\operatorname{poly}(N), where TT is the numerical time horizon, Armbruster et al. [1] obtain a factor 5/4+ε5/4+\varepsilon and Tong and Xu [8] obtain 21/17+ε21/17+\varepsilon, both for an arbitrary number of identical machines. Our algorithm enumerates a relaxation of constant order depending on ε\varepsilon. Writing εˉ=min⁡{ε,1}\bar{\varepsilon}=\min\{\varepsilon,1\}, Proposition 5.1 gives the explicit implementation bound n22O(1/εˉ)poly⁡(N)n^{2^{2O(1/\bar{\varepsilon})}}\operatorname{poly}(N).

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 DD blocks, where DD 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 aj,bja_j,b_j are the boundary marginals, hjh_j is the probability of duplication, cjc_j is its interior mass, and qj=1−aj−bj+hjq_j=1-a_j-b_j+h_j is the probability of boundary absence, the reservations are cj/qjc_j/q_j and hj/qjh_j/q_j when qj>0q_j>0. They fit together because aj+bj+cj≤1a_j+b_j+c_j\le1 implies cj+hj≤qjc_j+h_j\le q_j. 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 FiF_i for retained fractional mass, WiW_i for expected boundary duplication, and HiH_i for the repair-flow value of scheme ii. Up to accuracy losses, its expected matching value is at least

Fi−Wi+Hi.F_i-W_i+H_i.

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

Fi+1≥Fi−O(δF),Wi+1≤Hi+O(δF),F_{i+1}\ge F_i-O(\delta F),\qquad W_{i+1}\le H_i+O(\delta F),

where FF is the initial relaxation value and δ\delta is an internal accuracy parameter. The same quantity HiH_i rewards the current scheme and bounds the next scheme’s remaining duplication.

An accounting example. Ignore the accuracy losses and normalize FF to 12 units. The initial duplication bound is W0≤3W_0 \le3. After two coordination steps, W1≤H0W_1 \le H_0 and W2≤H1W_2 \le H_1. Set H2=0H_2 = 0 for the final scheme. The three scores are then bounded below by

9+H0,12−H0+H1,12−H1.9 + H_0,\qquad12 - H_0 + H_1,\qquad12 - H_1.

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, H0=2H_0 = 2 and H1=1H_1 = 1 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 e/(e−1)e/(e - 1) for job interval selection, whose formulation permits explicit intervals or intervals specified by job parameters. Im, Li, and Moseley [4] obtained a retained fraction α0−ε\alpha_0 - \varepsilon for a constant α0>0.6\alpha_0 > 0.6. 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 jj has an integral release time rjr_j, deadline djd_j, and positive integral processing time pjp_j. Its window is [rj,dj)[r_j,d_j). A schedule assigns each selected job one half-open execution interval of length pjp_j contained in its window; execution intervals must be disjoint. All numbers are given in binary. We write nn for the number of jobs, NN for the input encoding length, and OPT for the maximum number of scheduled jobs. Delete jobs with pj>dj−rjp_j > d_j-r_j, and solve instances with at most one job directly. A common translation of all times lets us assume rj≥0r_j \ge0. Put T=max⁡jdjT = \max_j d_j.

NotationMeaning
δ\delta, Q=δ−1Q = \delta^{-1}Loss parameter and integer number of portions or scales.
KK, D(K)D(K)Jobs per block; maximum number of blocks in a local table.
mim_i, β=Kmi\beta= Km_iGroup-size bound at step ii; jobs in one sampled group.
FF, FiF_iOriginal LP value; retained placement mass at step ii.
aja_j, bjb_j, cjc_jRetained release, deadline, and interior marginals of nonlocal job jj.
hjh_j, qjq_jProbabilities of two boundary copies and no boundary copy.
WiW_i, HiH_iTotal duplication probability and maximum repair flow at step ii.
Jact\mathcal{J}_{\mathrm{act}}, U\mathcal{U}Active jobs and the unprotected jobs identified by the residual cut.
MjM_j, VjV_jIndicators of no boundary copy and two boundary copies.
CintC_{\mathrm{int}}, JoutJ_{\mathrm{out}}Total retained interior mass and the algorithm’s output job set.
θ\theta, η\eta, κ(m)\kappa(m)Activity threshold, middle-arc capacity, and crossing-degree bound.
τ=6Q\tau= 6Q, Ji\mathcal{J}_iRefinement base and nested retained job sets in Appendix § 6.

Table 2. Principal notation. The per-job quantities aja_j, bjb_j, cjc_j, hjh_j, qjq_j and indicators MjM_j, VjV_j 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 Q≥100Q \ge100 and put δ=1/Q\delta= 1/Q. The same integer QQ will count the mass portions in rounding and the grouping scales in preprocessing. A block partition B\mathcal{B} divides [0,T)[0,T) into consecutive half-open intervals. A superblock partition S\mathcal{S} groups consecutive blocks. The release block of jj contains rjr_j; its deadline block [u,v)[u,v) is the unique block with dj∈(u,v]d_j \in(u,v]. 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 D(K)≥1D(K) \ge1 depending only on KK and δ\delta, a deterministic algorithm either solves the instance exactly or constructs δ−1\delta^{-1} candidate block–superblock partitions (Bℓ,Sℓ)(\mathcal{B}_\ell,\mathcal{S}_\ell), each with its own cap KℓK_\ell depending only on δ\delta and DD. For at least one candidate ℓ\ell, writing K=KℓK = K_\ell, B=Bℓ\mathcal{B} = \mathcal{B}_\ell, and S=Sℓ\mathcal{S} = \mathcal{S}_\ell, there is an eligible schedule J′J' that crosses no block boundary, uses at most KK jobs per block, and satisfies

∣J′∣≥(1−2δ)OPT⁡,∣B∣≤δ∣J′∣,KD(K)∣S∣≤δ3∣J′∣.(1)\lvert J' \rvert\ge(1-2\delta)\operatorname{OPT}, \qquad\lvert\mathcal{B} \rvert\le\delta\lvert J' \rvert, \qquad KD(K)\lvert\mathcal{S} \rvert\le\delta^3\lvert J' \rvert. \tag*{(1)}

The algorithm runs in nOδ(1)poly⁡(N)n^{O_\delta(1)}\operatorname{poly}(N) time, where the hidden constant may depend on the prescribed function DD.

The proof, including the dependence on DD, 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 ℓ\ell, write B,S\mathcal{B},\mathcal{S} for its partitions and abbreviate K=KℓK = K_\ell and D=D(Kℓ)D = D(K_\ell). Let CBC_B consist of all eligible job sets of size at most KK schedulable inside block BB. 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 BB. 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 BB. Thus the family can be constructed in nO(K)poly⁡(N)n^{O(K)}\operatorname{poly}(N) time per block. For nonempty U⊆BU \subseteq B of size at most DD, let TUT_U consist of tuples (CB)B∈U(C_B)_{B\in U} with CB∈CBC_B \in\mathcal{C}_B and with no job identity appearing twice.

The relaxation has a probability distribution xB,⋅x_{B,\cdot} on CB\mathcal{C}_B and a distribution μU\mu_U on TUT_U for every such UU. It imposes

∑C∈TU:CB=CμU(C)=xB,C(B∈U, C∈CB)(2)\sum_{\substack{C\in T_U:\\ C_B=C}} \mu_U(C)=x_{B,C}\qquad(B\in U,\ C\in\mathcal{C}_B) \tag*{(2)}
yj:=∑B∈B∑C∈CB:j∈CxB,C≤1(j∈J)(3)y_j:=\sum_{B\in B}\sum_{\substack{C\in\mathcal{C}_B:\\ j\in C}}x_{B,C}\le1\qquad(j\in\mathcal{J}) \tag*{(3)}

and maximizes F=∑jyjF=\sum_j y_j. Every distribution is nonnegative and normalized. The consistency constraints equate only the single-block marginals in (2).

Every candidate has O(n)O(n) blocks, as follows from the construction in Appendix § 6. Consequently the explicit LP has nO(KD)n^{O(KD)} variables and constraints. An eligible schedule with cap KK induces a feasible integral point, using the restriction of that schedule in every table. Solve each candidate’s LP with its own parameters KℓK_\ell and D(Kℓ)D(K_\ell), obtaining value FℓF_\ell. Discard candidate ℓ\ell if ∣Bℓ∣>δFℓ|B_\ell|>\delta F_\ell or KℓD(Kℓ)∣Sℓ∣>δ3FℓK_\ell D(K_\ell)|S_\ell|>\delta^3F_\ell, and choose a remaining candidate with largest value. From now on B,S,K,D,FB,S,K,D,F denote the selected partitions, parameters, and LP value. Lemma 2.1 ensures that at least one candidate survives and that the selected solution satisfies

F≥(1−2δ)OPT⁡,∣B∣≤δF,KD∣S∣≤δ3F.(4)F\ge(1-2\delta)\operatorname{OPT},\qquad|B|\le\delta F,\qquad KD|S|\le\delta^3F. \tag*{(4)}

From this point onward, FF denotes this fixed original LP value.

Coordinating the boundary blocks

A grouping QQ partitions a subset of the original blocks into sets of size at most m≤Dm\le D. Deleted blocks are not sampled. Independently for each G∈QG\in Q, sample a tuple from μG\mu_G 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 β=Km\beta=Km; any sampled group contains at most β\beta distinct jobs. Write F′F' for the sum of retained placement marginals.

For a nonlocal job jj, let aj,bja_j,b_j be its marginals in its retained release and deadline blocks, respectively, taking a marginal to be zero if the corresponding block was deleted. Let cjc_j be its total retained interior mass. Define

hj={ajbj,if both boundary blocks survive in distinct groups,0,otherwise,h_j= \begin{cases} a_jb_j, & \text{if both boundary blocks survive in distinct groups},\\ 0, & \text{otherwise}, \end{cases}
qj=1−aj−bj+hj,W=∑jhj.(5)q_j=1-a_j-b_j+h_j,\qquad W=\sum_j h_j. \tag*{(5)}

The table for a group never repeats a job; different groups are sampled independently. Hence hjh_j is the probability that both boundaries contain jj, and qjq_j is the probability that neither does. In particular,

cj+hj≤qj,W≤F′/4≤F/4.(6)c_j+h_j\le q_j,\qquad W\le F'/4\le F/4. \tag*{(6)}

The first inequality is equivalent to aj+bj+cj≤1a_j+b_j+c_j\le1. For the second, hj≤(aj+bj)2/4≤(aj+bj)/4h_j\le(a_j+b_j)^2/4\le(a_j+b_j)/4, since aj+bj≤1a_j+b_j\le1. All sums over boundary pairs below are over nonlocal jobs.

Set θ=δ2\theta= \delta^2 and η=δ6/β\eta= \delta^6/\beta. Let Jact={j:hj≥θ}\mathcal{J}_{\mathrm{act}} = \{j : h_j \ge\theta\} be the set of active jobs. Two boundary pairs cross when their four blocks strictly interleave in chronological order. Orient a crossing j→kj \to k if pj≤pkp_j \le p_k, with any fixed tie-breaking order on job identities. One boundary block of kk lies strictly between the two boundary blocks of jj, and is therefore entirely contained in [rj,dj)[r_j,d_j). The execution slot of kk in that block can accommodate jj. 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 Bk,LB_{k,L} lies in the window of jj. A slot generated by kk in this block can therefore serve jj when pj≤pkp_j \le p_k. The opposite interleaving order uses Bk,RB_{k,R}. 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 ss, sink tt, left and right copies jL,jRj_L,j_R of each active job, arcs s→jLs \to j_L and jR→tj_R \to t of capacity hjh_j, and an arc jL→kRj_L \to k_R of capacity η\eta for each permitted crossing j→kj \to k. Let ujku_{jk} be a maximum flow on the middle arcs and HH its value. In particular,

0≤ujk≤η,∑kujk≤hj,∑jujk≤hk,H=∑jkujk.(7)0 \le u_{jk} \le\eta,\qquad\sum_k u_{jk} \le h_j,\qquad\sum_j u_{jk} \le h_k,\qquad H = \sum_{jk} u_{jk}. \tag*{(7)}

Let XX and YY be the sets of reachable left and right copies, respectively, in the residual graph from ss. Define

U={j∈Jact:jL∉X or jR∈Y}.U = \{j \in\mathcal{J}_{\mathrm{act}} : j_L \notin X \text{ or } j_R \in Y\}.

Protect every job in Jact∖U\mathcal{J}_{\mathrm{act}} \setminus U. 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 bb vertices, each with at most κ\kappa crossings per edge, suppose the first graph has components of size at most mm. For any integer M≥1M \ge1, we can delete whole components of the first graph, containing at most

140c(κ)mbM vertices,c(κ)=1+2κ(κ+1),(8)\frac{140c(\kappa)mb}{\sqrt{M}}\text{ vertices},\qquad c(\kappa) = 1 + 2\kappa(\kappa+ 1), \tag*{(8)}

so that every remaining component of their union has size at most MM. Crossings here refer to chords with strictly interleaved endpoints; edges sharing an endpoint do not cross.

Define the constants

κ(m)=4Kmδ−6,m0=1,mi+1=[280Kmic(κ(mi))]2 (i=0,1),D(K)=m2.(9)\kappa(m) = 4Km\delta^{-6},\qquad m_0 = 1,\qquad m_{i+1} = [280Km_i c(\kappa(m_i))]^2\ (i = 0,1),\qquad D(K) = m_2. \tag*{(9)}

They are integers because δ−1\delta^{-1} is an integer. This is the function DD used in preprocessing and in the LP.

Initially every block is a singleton group, and the old graph is edgeless. At step i∈{0,1}i \in\{0,1\}, compute the network and protected graph for the current grouping. Apply (8) to the old graph and protected graph with m=mim=m_i, κ=κ(mi)\kappa=\kappa(m_i), and M=mi+1M=m_{i+1}. 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 FiF_i, WiW_i, HiH_i for the retained mass, duplication mass, and maximum flow at step ii, and put H2=0H_2=0.

Lemma 3.1 (Coordination). Each of the two steps is well-defined and satisfies

Fi+1≥Fi−δF/2,Wi+1≤Hi+δF/2.(10)F_{i+1} \ge F_i-\delta F/2,\qquad W_{i+1} \le H_i+\delta F/2. \tag*{(10)}

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 ss in the residual network of a maximum flow. If jL∉Xj_L \notin X, then s→jLs \to j_L has no positive residual capacity; otherwise that arc would make jLj_L reachable. Its flow is therefore hjh_j. Similarly, jR∈Yj_R \in Y implies that jR→tj_R \to t is saturated, since a positive residual capacity would make tt reachable.

These two saturation statements alone would allow a factor-two bound. The following disjointness avoids that loss. If jL∉Xj_L \notin X and kR∈Yk_R \in Y, then ujk=0u_{jk}=0: positive flow would create the reverse residual arc kR→jLk_R \to j_L, making jLj_L reachable. Consequently,

∑j∈Jact:jL∉Xhj=∑j,k:jL∉Xujk,\sum_{j\in\mathcal{J}_{\mathrm{act}}:j_L\notin X} h_j = \sum_{j,k:j_L\notin X}u_{jk},
∑k∈Jact:kR∈Yhk=∑j,k:kR∈Yujk.\sum_{k\in\mathcal{J}_{\mathrm{act}}:k_R\in Y} h_k = \sum_{j,k:k_R\in Y}u_{jk}.

count disjoint sets of positive middle-arc flows. A job in both defining classes of UU is counted twice on the left below, which only increases the bound. Thus

∑j∈Uhj≤∑j∈Jact:jL∉Xhj+∑j∈Jact:jR∈Yhj≤Hi.(11)\sum_{j\in U}h_j \le \sum_{j\in\mathcal{J}_{\mathrm{act}}:j_L\notin X}h_j + \sum_{j\in\mathcal{J}_{\mathrm{act}}:j_R\in Y}h_j \le H_i. \tag*{(11)}

This is the source of the large-flow/small-duplication tradeoff: protecting all other active pairs leaves at most HiH_i active duplicate mass unpaid.

Protected edges have bounded crossing degree. For protected jobs j,kj,k, a permitted arc jL→kRj_L\to k_R goes from a reachable vertex to an unreachable one. It must be saturated, so ujk=ηu_{jk}=\eta. The total flow incident to the left and right copies of one job is at most 2hj≤22h_j\le2. There are therefore at most 2/η2/\eta 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 aj,bj≥θa_j,b_j\ge\theta: their product is at least θ\theta, and neither factor exceeds one. A group has expected total placement count at most β=Km\beta=Km. At most β/θ\beta/\theta active jobs can consequently have a boundary in any one group. The nonpermitted crossings of the fixed pair number at most 2β/θ2\beta/\theta. Combining the two cases yields

2η+2βθ≤4δ−6=κ(mi).\frac{2}{\eta}+\frac{2\beta}{\theta}\le4\delta^{-6}=\kappa(m_i).

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 m1m_1. Its crossing degree is at most κ(1)≤κ(m1)\kappa(1) \le\kappa(m_1). The second protected graph has crossing degree at most κ(m1)\kappa(m_1) by the preceding argument. These are exactly the two applications for which the hypotheses of Lemma B.2 have been established.

At step ii, the separator removes at most 140c(κ(mi))mi∣B∣/mi+1140c(\kappa(m_i))m_i|\mathcal{B}|/\sqrt{m_{i+1}} blocks; we used the original number of blocks to upper-bound the current number. Each block has placement mass at most KK, since every one of its configurations has at most KK jobs. The choice of mi+1m_{i+1} gives

K140c(κ(mi))mi∣B∣mi+1=∣B∣2≤δF2.K\frac{140c(\kappa(m_i))m_i|\mathcal{B}|}{\sqrt{m_{i+1}}}=\frac{|\mathcal{B}|}{2}\le\frac{\delta F}{2}.

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 ajbja_jb_j to zero; deleting an endpoint also changes it to zero. Thus no pair’s duplication probability increases. Active unprotected pairs contribute at most HiH_i by (11). For an inactive pair, hj<δ2h_j<\delta^2 and 2hj≤aj+bj2\sqrt{h_j}\le a_j+b_j, including the case hj=0h_j=0. Hence hj≤δ(aj+bj)/2h_j\le\delta(a_j+b_j)/2. Summing over those pairs gives at most δFi/2≤δF/2\delta F_i/2\le\delta F/2. 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 t≥1t\ge1, put vertices in cyclic order

x,a1,…,at,y,bt,…,b1.x,a_1,\ldots,a_t,y,b_t,\ldots,b_1.

The family consisting of xyxy and the family consisting of the nested edges aibia_ib_i are each crossing-free. Their union is a matching, so each component has two vertices, but xyxy crosses all tt 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 tt steps with the same bounds as Lemma 3.1, and apply Lemma 4.1 to all t+1t+1 groupings. Put Ht=0H_t = 0. The same calculation would give

∑i=0t(Fi−Wi+Hi)≥∑i=0tFi−W0−tδF2,\sum_{i=0}^{t}(F_i-W_i+H_i)\ge\sum_{i=0}^{t}F_i-W_0-\frac{t\delta F}{2},
E∣Jout∣≥(1−14(t+1)−δ(4+t4+t2(t+1)))F.\mathbb{E}|J_{\mathrm{out}}|\ge\left(1-\frac{1}{4(t+1)}-\delta\left(4+\frac{t}{4}+\frac{t}{2(t+1)}\right)\right)F.

Here Fi≥F−iδF/2F_i \ge F-i\delta F/2 and W0≤F/4W_0 \le F/4 explain every term in the second line. Under these hypotheses, extending the structural argument to more rounds would therefore improve the approximation ratio.

Two drawings comparing separate pages with a union drawn on one page

Figure 2. Why the established pagewise bounds do not automatically apply to the accumulated old graph. In the order x,a1,…,at,y,bt,…,b1x,a_1,\ldots,a_t,y,b_t,\ldots,b_1, the two matchings G0={xy}G_0=\{xy\} and G1={aibi:1≤i≤t}G_1=\{a_i b_i:1\le i\le t\} are each crossing-free. Their union has only two-vertex components, but xyxy crosses all tt other edges in a common one-page drawing. The case t=3t=3 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 [s,t)[s,t). A job jj is compatible with the slot if

min⁡{t,dj}−max⁡{s,rj}≥pj.(12)\min\{t,d_j\}-\max\{s,r_j\}\ge p_j. \tag*{(12)}

Compute a maximum bipartite matching between all jobs and all slots. An assigned job starts at max⁡{s,rj}\max\{s,r_j\}. 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 m≤Dm \le D, and any nonnegative weights on permitted crossings satisfying (7), the expected maximum matching cardinality is at least

F′−W+H−4δF.F' - W + H - 4\delta F.

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 β\beta 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 jj, let Tj∈{0,1}T_j \in\{0,1\} be determined only by its occurrence records in a fixed set of at most two groups. If 0≤wj≤a0 \le w_j \le a, then

Var⁡(∑jwjTj)≤4βa E[∑jwjTj].\operatorname{Var}\left(\sum_j w_jT_j\right) \le4\beta a\,\mathbb{E}\left[\sum_j w_jT_j\right].

Proof. Write Z=∑jwjTjZ=\sum_j w_jT_j. If 0<Pr⁡(Tj=1)<10<\Pr(T_j=1)<1, couple the conditional experiments given Tj=1T_j=1 and Tj=0T_j=0 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 4β4\beta 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 ZZ differ in absolute value by at most 4βa4\beta a, and

Cov⁡(Tj,Z)=Pr⁡(Tj=1)Pr⁡(Tj=0)(E[Z∣Tj=1]−E[Z∣Tj=0])≤4βaETj.\operatorname{Cov}(T_j,Z)=\Pr(T_j=1)\Pr(T_j=0)\bigl(\mathbb{E}[Z\mid T_j=1]-\mathbb{E}[Z\mid T_j=0]\bigr)\le4\beta a\mathbb{E}T_j.

If TjT_j is constant, its covariance is zero. Finally sum these inequalities with weights wjw_j, using Var⁡(Z)=∑jwjCov⁡(Tj,Z)\operatorname{Var}(Z)=\sum_j w_j\operatorname{Cov}(T_j,Z).

Constructing the fractional matching

Proof of Lemma 4.1. Let MjM_j and VjV_j indicate boundary absence and boundary duplication. Then EMj=qj\mathbb{E}M_j=q_j and EVj=hj\mathbb{E}V_j=h_j. The baseline counts each sampled local job and each boundary-present nonlocal job exactly once. Writing Cint=∑jcjC_{\mathrm{int}}=\sum_j c_j, its expected size is F′−Cint−WF^{\prime}-C_{\mathrm{int}}-W. Its actual assignment to boundary slots will be completed after repairs. For each absent nonlocal job reserve capacity cj/qjc_j/q_j for interior assignments and hj/qjh_j/q_j for boundary repairs. Their sum is at most one by (6). Whenever qj=0q_j=0, 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.

AccountAssigned massCapacity check
Absent recipient jjInterior at most (cj/qj)Mj(c_j/q_j)M_j; repairs at most (hj/qj)Mj(h_j/q_j)M_jSum at most MjM_j, since cj+hj≤qjc_j+h_j\le q_j.
Duplicated donor kkRepairs export at most VkV_k in total from its two boundary slotsIf Vk=1V_k=1, two unit slots retain at least one unit for kk. Each slot exports at most one.
Other baseline jobsOne unit for each sampled local job or job with exactly one boundary copyIts own sampled slot supplies that unit.
Interior slotsUsed only for absent recipientsThe 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 C>0C>0. Let cj,Sc_{j,S} be the retained interior mass of jj in this superblock. Sort these masses by nonincreasing processing time, breaking ties arbitrarily, and split the resulting mass interval into QQ consecutive portions, each of mass zS=δCz_S = \delta C. A job’s mass may straddle a cut. Let cj,gc_{j,g} be its mass in portion gg. Define the demand

Ng=∑j(cj,g/qj)Mj.N_g = \sum_j (c_{j,g}/q_j)M_j.

For every sampled interior slot generated by jj in this superblock, allocate the fraction cj,g/cj,Sc_{j,g}/c_{j,S} to supply for portion gg; let the resulting total supply be UgU_g. Terms with cj,S=0c_{j,S}=0 are absent. The fractions over all portions sum to one for every such slot. Both NgN_g and UgU_g have expectation zSz_S, by the preserved one-block marginals. Each demand coefficient is at most one, so Lemma 4.2 gives Var⁡(Ng)≤4βzS\operatorname{Var}(N_g) \le4\beta z_S. Write UgU_g as a sum of independent group contributions in [0,β][0,\beta]. For a variable V∈[0,β]V \in[0,\beta], Var⁡(V)≤EV2≤βEV\operatorname{Var}(V) \le\mathbb{E}V^2 \le\beta\mathbb{E}V, hence Var⁡(Ug)≤βzS\operatorname{Var}(U_g) \le\beta z_S.

For g≥2g \ge2, every demanded job in portion gg has processing time at most the length of every slot supplying portion g−1g-1. 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 min⁡{Ng,Ug−1}\min\{N_g,U_{g-1}\}. The following estimate holds for arbitrary dependence between demand and supply:

Emin⁡{Ng,Ug−1}=zS−12E∣Ng−Ug−1∣≥zS−12(Var⁡(Ng)+Var⁡(Ug−1))≥zS−32βzS.\begin{aligned} \mathbb{E}\min\{N_g,U_{g-1}\} = z_S - \frac{1}{2}\mathbb{E}|N_g-U_{g-1}| \\ &\ge z_S - \frac{1}{2}\left(\sqrt{\operatorname{Var}(N_g)}+\sqrt{\operatorname{Var}(U_{g-1})}\right) \ge z_S-\frac{3}{2}\sqrt{\beta z_S}. \end{aligned}

Summing g=2,…,Qg=2,\ldots,Q and using 32βC/δ≤δC+9β/(16δ2)\frac{3}{2}\sqrt{\beta C/\delta}\le\delta C+9\beta/(16\delta^2) gives an expected contribution of at least (1−2δ)C−9β/(16δ2)(1-2\delta)C-9\beta/(16\delta^2). A zero-mass superblock needs no assignment and satisfies the same lower bound. Summing over superblocks, and using β≤KD\beta\le KD and (4), the expected interior contribution is at least

Cint−2δCint−9β∣S∣16δ2≥Cint−4116δF≥Cint−3δF.(13)C_{\mathrm{int}}-2\delta C_{\mathrm{int}}-\frac{9\beta|S|}{16\delta^2} \ge C_{\mathrm{int}}-\frac{41}{16}\delta F \ge C_{\mathrm{int}}-3\delta F. \tag*{(13)}

Each supply portion is used at most once. The total demand assigned to job jj over all superblocks is at most (cj/qj)Mj(c_j/q_j)M_j, so all interior assignments respect the reserved capacities.

Boundary repairs. For each positive-weight permitted pair propose a transfer

Pjk=ujkqjhkMjVk.P_{jk}=\frac{u_{jk}}{q_jh_k}M_jV_k.

Positive weights imply qj≥hj≥θq_j\ge h_j\ge\theta and hk≥θh_k\ge\theta. The four determining groups are distinct, so MjM_j and VkV_k are independent and EPjk=ujk\mathbb{E}P_{jk}=u_{jk}. Let Xj=∑kPjkX_j=\sum_kP_{jk} and Yk=∑jPjkY_k=\sum_jP_{jk}. Scale any overloaded row down to capacity (hj/qj)Mj(h_j/q_j)M_j, and then scale any overloaded column down to capacity VkV_k. Column scaling cannot increase a row sum. The total removed mass is at most the sum of the original row and column excesses.

Put uj+=∑kujku_j^+=\sum_k u_{jk} and uk−=∑jujku_k^-=\sum_j u_{jk}. Conditional on Mj=1M_j=1, every flag VkV_k in row jj depends only on groups outside jj’s two boundary groups. Its joint distribution with the other row flags is consequently unchanged by this conditioning. Applying Lemma 4.2 with weights ujk/hk≤η/θu_{jk}/h_k\le\eta/\theta gives

E[Xj∣Mj=1]=uj+/qj≤hj/qj,Var⁡(Xj∣Mj=1)≤4βηuj+qj2θ.\mathbb{E}[X_j\mid M_j=1]=u_j^+/q_j\le h_j/q_j,\qquad \operatorname{Var}(X_j\mid M_j=1)\le\frac{4\beta\eta u_j^+}{q_j^2\theta}.

The same argument for a column, conditioning on Vk=1V_k=1 and using weights ujk/qj≤η/θu_{jk}/q_j\le\eta/\theta, gives

E[Yk∣Vk=1]=uk−/hk≤1,Var⁡(Yk∣Vk=1)≤4βηuk−hk2θ.\mathbb{E}[Y_k\mid V_k=1]=u_k^-/h_k\le1,\qquad \operatorname{Var}(Y_k\mid V_k=1)\le\frac{4\beta\eta u_k^-}{h_k^2\theta}.

If EZ≤tEZ \le t, then E(Z−t)+≤E∣Z−EZ∣≤Var⁡(Z)\mathbb{E}(Z-t)_{+} \le\mathbb{E}|Z-EZ| \le\sqrt{\operatorname{Var}(Z)}. Multiplying the conditional bounds by qjq_j and hkh_k, respectively, bounds expected row and column losses by 2βηuj+/θ2\sqrt{\beta\eta u_j^{+}/\theta} and 2βηuk−/θ2\sqrt{\beta\eta u_k^{-}/\theta}. There are at most F/(4θ)F/(4\theta) active jobs, by (6), and H≤W≤F/4H \le W \le F/4. Cauchy–Schwarz therefore bounds total expected loss by

4βη/θF4θH≤Fβηθ=δF.(14)4\sqrt{\beta\eta/\theta}\sqrt{\frac{F}{4\theta}H}\le\frac{F\sqrt{\beta\eta}}{\theta}=\delta F. \tag*{(14)}

This also covers H=0H=0, 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 pj≤pkp_j \le p_k. Fix a duplicated donor kk. 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 e1,e2e_1,e_2, their unused capacities satisfy (1−e1)+(1−e2)≥1(1-e_1)+(1-e_2)\ge1. Assign one unit of kk across these unused capacities, for example 1−e11-e_1 on the first slot and e1e_1 on the second. This is feasible because e1≤1−e2e_1\le1-e_2. The job kk 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 (cj/qj)Mj+(hj/qj)Mj≤Mj(c_j/q_j)M_j+(h_j/q_j)M_j\le M_j, 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

(F′−Cint−W)+(Cint−3δF)+(H−δF)=F′−W+H−4δF.(F^{\prime}-C_{\mathrm{int}}-W)+(C_{\mathrm{int}}-3\delta F)+(H-\delta F)=F^{\prime}-W+H-4\delta F.

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 Bi=[4(i−1),4i)B_i=[4(i-1),4i), i=1,…,5i=1,\ldots,5, each forming its own superblock and sampling group, and two jobs

(rj,dj,pj)=(1,15,1),(rk,dk,pk)=(5,19,2).(r_j,d_j,p_j)=(1,15,1),\qquad(r_k,d_k,p_k)=(5,19,2).

Consider a distribution that places jj in B1,B3,B4B_1,B_3,B_4 with probabilities 1/4,1/2,1/41/4,1/2,1/4, respectively, and independently places kk in B2B_2 or B5B_5, each with probability 1/21/2. Use execution intervals [1,2),[8,9),[12,13)[1,2),[8,9),[12,13) for the three placements of jj, and [5,7),[16,18)[5,7),[16,18) for those of kk. 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 jj, the boundary and interior masses are aj=bj=1/4a_j=b_j=1/4 and cj=1/2c_j=1/2, so

hj=1/16,qj=9/16,cj/qj=8/9,hj/qj=1/9.h_j=1/16,\qquad q_j=9/16,\qquad c_j/q_j=8/9,\qquad h_j/q_j=1/9.

A boundary-absent job jj 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 kk, duplication has probability hk=1/4h_k = 1/4. Its B2B_2 slot can accommodate jj, since the boundary pairs B1,B4B_1, B_4 and B2,B5B_2, B_5 cross and pj≤pkp_j \le p_k. For the permitted flow weight ujk=ηu_{jk} = \eta, the proposed transfer on the event Mj=Vk=1M_j = V_k = 1 is 64η/964\eta/9. This is at most 1/91/9, since η=δ6/β≤1/64\eta= \delta^6/\beta\le1/64, and so neither row nor column scaling is needed in this example. Its expectation is exactly η\eta. On that event the duplicated kk keeps one unit in its B5B_5 slot, while the repair uses at most one unit of its B2B_2 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 si=Fi−Wi+His_i = F_i - W_i + H_i for i=0,1,2i = 0,1,2, with H2=0H_2 = 0. Choose a grouping with maximum score, sample its groups independently from their local tables, and return a maximum compatible job–slot matching. Let JoutJ_{\mathrm{out}} 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 F0=FF_0 = F and W0≤F/4W_0 \le F/4. Lemma 3.1 gives

∑i=02si=F0+F1+F2−W0+(H0−W1)+(H1−W2)≥F0+F1+F2−W0−δF≥3F−W0−52δF.\begin{aligned} \sum_{i=0}^{2} s_i &= F_0 + F_1 + F_2 - W_0 + (H_0 - W_1) + (H_1 - W_2) \\ &\ge F_0 + F_1 + F_2 - W_0 - \delta F \\ &\ge3F - W_0 - \frac{5}{2}\delta F. \end{aligned}

By Lemma 4.1, choosing a grouping with maximum score yields

∣Jout∣≥F−W0/3−296δF≥(11/12−29δ/6)F≥(11/12−7δ)OPT.\lvert J_{\mathrm{out}}\rvert\ge F - W_0/3 - \frac{29}{6}\delta F \ge(11/12 - 29\delta/6)F \ge(11/12 - 7\delta)\mathrm{OPT}.

For the last inequality, the coefficient of FF is positive and (4) applies; expanding the product loses at most (29/6+11/6)δ=(20/3)δ<7δ(29/6 + 11/6)\delta= (20/3)\delta< 7\delta.

It remains to account for finite random bits and binary arithmetic. Set εˉ=min⁡{ε,1}\bar{\varepsilon} = \min\{\varepsilon,1\} and δ=1/⌈100+1000/εˉ⌉\delta= 1/\lceil100 + 1000/\bar{\varepsilon}\rceil. All caps, refinement depths, group sizes, and table orders are constants depending only on ε\varepsilon. Greedy earliest-completion computations and feasibility checks use addition, maximum, and comparison of binary endpoints. Their intermediate numbers have encoding length polynomial in NN and log⁡n\log n; no algorithm enumerates the numerical time horizon. The explicit rational LP has polynomial size for fixed ε\varepsilon, 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 Rs≥1R_s \ge1 independent draws and each table has support at most Ss≥1S_s \ge1. Put b=⌈log⁡2(nRsSs/δ)⌉b = \lceil\log_2(nR_sS_s/\delta)\rceil. Round each table probability down to a multiple of 2−b2^{-b} and assign the remaining probability to one outcome that originally had positive probability. The resulting distribution has total-variation distance at most Ss2−bS_s2^{-b} from the original distribution. The product distributions have distance at most RsSs2−b≤δ/nR_sS_s2^{-b} \le\delta/n, by coupling the draws independently. Output cardinality lies in [0,n][0,n], so expected cardinality falls by at most δ\delta. Sampling each rounded table uses exactly bb 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 OPT⁡≥1\operatorname{OPT} \ge1, the implemented algorithm retains at least (11/12−8δ)OPT⁡(11/12 - 8\delta)\operatorname{OPT} in expectation. Finally,

1112−112/11+ε=121ε12(12+11ε)≥121εˉ276>8δ.\frac{11}{12}-\frac{1}{12/11+\varepsilon}=\frac{121\varepsilon}{12(12+11\varepsilon)}\ge\frac{121\bar{\varepsilon}}{276}>8\delta.

The algorithm therefore has the claimed approximation factor and running time nOε(1)poly⁡(N)n^{O_{\varepsilon}(1)}\operatorname{poly}(N).

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 εˉ=min⁡{ε,1}\bar{\varepsilon}=\min\{\varepsilon,1\}, the one-machine algorithm can be implemented in

n2O(1/εˉ)poly⁡(N)n^{2^{O(1/\bar{\varepsilon})}}\operatorname{poly}(N)

time for n≥2n\ge2. 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 MM. Keep Q=δ−1Q=\delta^{-1} and define the absolute constant C0=224002C_0=22400^2. The parameter definitions in (9) give κ(m)=4Kmδ−6≥1\kappa(m)=4Km\delta^{-6}\ge1 and c(κ)=1+2κ(κ+1)≤5κ2c(\kappa)=1+2\kappa(\kappa+1)\le5\kappa^2. Hence

mi+1≤[280Kmi⋅5(4Kmiδ−6)2]2=C0K6mi6δ−24,m_{i+1}\le\left[280Km_i\cdot5(4Km_i\delta^{-6})^2\right]^2=C_0K^6m_i^6\delta^{-24},

and, since m0=1m_0=1 and D(K)=m2D(K)=m_2,

D(K)≤C07K42δ−168.(15)D(K)\le C_0^7K^{42}\delta^{-168}. \tag*{(15)}

The preprocessing cap is K0=(6Q)6Q+3K_0=(6Q)^{6Q+3}, so log⁡2K0=O(Qlog⁡Q)\log_2K_0=O(Q\log Q). Write Kℓ=K0aℓK_\ell=K_0a_\ell and a1=4a_1=4. The least multiple of aℓa_\ell above a real threshold u≥aℓu\ge a_\ell is at most u+aℓ≤2uu+a_\ell\le2u. In the scale recurrence the threshold 4KℓD(Kℓ)/δ24K_\ell D(K_\ell)/\delta^2 dominates 2aℓ2a_\ell. Applying (15) therefore yields

aℓ+1≤8C0K07Q170aℓ43=B0aℓ43,log⁡2B0=O(Qlog⁡Q).a_{\ell+1}\le8C_0K_0^7Q^{170}a_\ell^{43}=B_0a_\ell^{43},\qquad\log_2B_0=O(Q\log Q).

Iterating log⁡2aℓ+1≤43log⁡2aℓ+log⁡2B0\log_2a_{\ell+1}\le43\log_2a_\ell+\log_2B_0 for QQ steps gives the explicit estimate

log⁡2aQ+1≤2⋅43Q+43Q−142log⁡2B0≤43Q(2+log⁡2B042)=2O(Q).\log_2a_{Q+1}\le2\cdot43^Q+\frac{43^Q-1}{42}\log_2B_0\le43^Q\left(2+\frac{\log_2B_0}{42}\right)=2^{O(Q)}.

It follows that all candidate caps KℓK_\ell, table orders D(Kℓ)D(K_\ell), and the exact-enumeration cutoff R=⌈max⁡{(6Q)3,2K0aQ+1}⌉R=\left\lceil\max\{(6Q)^3,2K_0a_{Q+1}\}\right\rceil are at most 22O(Q)2^{2^{O(Q)}}. Enumerating all ordered job subsets up to the cutoff costs nO(R)n^{O(R)} times a polynomial in the binary input length. The local relaxation has nO(KℓD(Kℓ))n^{O(K_\ell D(K_\ell))} entries and constraints, and all remaining computations are polynomial in this explicit representation and NN. There are only QQ candidates. Parameter construction and factors depending only on QQ can also be absorbed into the displayed bound for n≥2n\ge2. Thus the total time is n2O(Q)poly⁡(N)n^{2^{O(Q)}}\operatorname{poly}(N). Finally the choice in the theorem proof has Q=⌈100+1000/εˉ⌉=O(1/εˉ)Q=\lceil100+1000/\bar{\varepsilon}\rceil=O(1/\bar{\varepsilon}).

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 DD.

Greedy refinement

For an interval BB and a supplied set of job identities EE, write Greedy⁡(B,E)\operatorname{Greedy}(B,E) for the following subroutine. Make a fresh working copy of EE. Repeatedly select from that copy a job with earliest feasible completion in BB, 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 EE 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 [u,v)[u,v) is a feasible execution of such a job inside the run’s interval, then some greedy completion belongs to (u,v](u,v]. Indeed, just after the last greedy completion at or before uu, or at the left endpoint if none exists, that execution is an available candidate. Thus either the next greedy completion is at most uu, contradicting its choice as the last one, or it lies in (u,v](u,v]. If there is no next selection, the available candidate contradicts termination. Disjoint executions have disjoint intervals (u,v](u,v], so charging each execution in this way defines an injection into the greedy completions.

Put τ=6Q=6/δ\tau= 6Q = 6/\delta, Li=τi+2L_i = \tau^{i+2}, and K0=ττ+3K_0 = \tau^{\tau+3}. Run Greedy⁡([0,T),J)\operatorname{Greedy}([0,T),J), and let J1J_1 be its selected identity set; retain the resulting execution intervals as well. Cut after every L1L_1 selected jobs, except after the final selected job. For every iteration i≥2i \ge2, carry out the following scan.

  1. Reset the iteration’s availability set to Ei:=Ji−1E_i := J_{i-1} and initialize Ji:=∅J_i := \varnothing. No removal from a previous iteration is carried over: its selected identities are precisely the new input set.

  1. Visit the blocks present at the start of iteration ii, from left to right. For a parent block BB, compute the tentative schedule PB:=Greedy⁡(B,Ei)P_B := \operatorname{Greedy}(B,E_i). Its construction modifies only the subroutine’s fresh working copy.

  1. If ∣PB∣>Li|P_B| > L_i, keep its execution intervals, add its identities to JiJ_i, and replace EiE_i by Ei∖PBE_i \setminus P_B. Subdivide BB after every LiL_i selected jobs, except after the final selected job. The resulting children are not scanned again at this iteration.

  1. If ∣PB∣≤Li|P_B| \le L_i, discard the tentative schedule and leave EiE_i 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 EiE_i before the next parent run. Their union is therefore a feasible schedule on the identity set JiJ_i. Every identity considered during iteration ii belongs to Ji−1J_{i-1}, proving Ji⊆Ji−1J_i \subseteq J_{i-1}. Stop at the first iteration with ∣Ji−1∖Ji∣≤∣J1∣/τ|J_{i-1} \setminus J_i| \le|J_1|/\tau. Such an iteration exists by i=τ+1i = \tau+ 1: otherwise the τ\tau disjoint differences for i=2,…,τ+1i = 2,\ldots,\tau+1 would contain more than ∣J1∣|J_1| jobs.

Let R1=J∖J1R_1 = J \setminus J_1 and Rj=Jj−1∖JjR_j = J_{j-1} \setminus J_j for j≥2j \ge2. In any schedule lying within a block after iteration jj, at most 2Lj2L_j jobs belong to RjR_j. For j=1j = 1, all these jobs were unselected, and the charging observation bounds their count by the at most L1L_1 greedy completions in the block. For j≥2j \ge2, each identity in RjR_j belongs to the reset set Ej=Jj−1E_j = J_{j-1} and to no schedule committed in iteration jj. It is consequently present in EjE_j 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 EjE_j unchanged. In a kept child, all RjR_j jobs were unselected in that parent’s run, and charge to at most LjL_j completions in that child. In an unkept parent, at most LjL_j jobs are identities of its tentative schedule; all remaining jobs charge to at most LjL_j completions. The bound also holds in all finer blocks produced later. The number of cuts created throughout the construction is at most

∑j≥1∣Jj∣/Lj≤OPT⁡∑j≥1τ−j−2≤2OPT⁡/τ3.\sum_{j\ge1} |J_j|/L_j \le\operatorname{OPT}\sum_{j\ge1}\tau^{-j-2} \le2\operatorname{OPT}/\tau^3.

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 2OPT⁡/τ32\operatorname{OPT}/\tau^3 jobs. Let ii be the stopping iteration. Remove from this aligned schedule all identities in Ji−1J_{i-1}, clear all kept parents of iteration ii, and insert JiJ_i in those parents. Removing Ji−1J_{i-1} and inserting JiJ_i has net loss at most ∣Ji−1∖Ji∣≤OPT⁡/τ|J_{i-1} \setminus J_i| \le\operatorname{OPT}/\tau. After removing Ji−1J_{i-1}, the remaining identities belong to R1,…,Ri−1R_1,\ldots,R_{i-1}. Every kept parent therefore contains at most

2∑j<iLj≤4Li/τ2\sum_{j<i} L_j \le4L_i/\tau

of them. Each kept parent contributes more than LiL_i jobs to JiJ_i; there are at most OPT⁡/Li\operatorname{OPT}/L_i kept parents. Clearing them loses at most 4OPT⁡/τ4\operatorname{OPT}/\tau more jobs. The resulting aligned schedule J′′J'' consequently satisfies

∣J′′∣≥(1−6/τ)OPT⁡=(1−δ)OPT⁡.(16)|J''| \ge(1-6/\tau)\operatorname{OPT}=(1-\delta)\operatorname{OPT}. \tag*{(16)}

Each kept child contains only its inserted jobs, at most LiL_i of them. An unkept parent contains at most 4Li/τ≤Li4L_i/\tau\le L_i remaining jobs. Thus every final block has at most Li≤K0L_i \le K_0 jobs of J′′J''. Denote this fine partition by B0\mathcal{B}_0 and its size by b0b_0. If OPT⁡≥τ3\operatorname{OPT}\ge\tau^3, the cut bound gives

b0≤3OPT⁡/τ3.(17)b_0 \le3\operatorname{OPT}/\tau^3. \tag*{(17)}

The number of cuts is also O(n)O(n), since every JjJ_j has at most nn jobs and τ\tau is a constant.

Nested grouping scales

Recall that Q=δ−1Q=\delta^{-1} and set a1=4a_1=4. Recursively choose aℓ+1a_{\ell+1} to be the least positive multiple of aℓa_\ell satisfying

aℓ+1≥max⁡{2aℓ,4KℓD(Kℓ)/δ2},Kℓ=K0aℓ,ℓ=1,…,Q.a_{\ell+1} \ge\max\{2a_\ell,4K_\ell D(K_\ell)/\delta^2\}, \qquad K_\ell=K_0a_\ell,\quad\ell=1,\ldots,Q.

All these numbers depend only on δ\delta and the prescribed function DD. Let R=⌈max⁡{τ3,2K0aQ+1}⌉R=\lceil\max\{\tau^3,2K_0a_{Q+1}\}\rceil. Enumerate all subsets and orders through size R+1R+1, using earliest-start feasibility tests. If no feasible schedule of size R+1R+1 exists, these tests return an exact optimum, since any larger schedule would contain such a subset. Otherwise OPT⁡>R\operatorname{OPT}>R and the preceding construction gives

b0≥∣J′′∣/K0≥(1−δ)OPT⁡/K0≥aQ+1.b_0 \ge|J''|/K_0 \ge(1-\delta)\operatorname{OPT}/K_0 \ge a_{Q+1}.

For candidate ℓ\ell, form blocks from consecutive batches of aℓa_\ell fine blocks and superblocks from batches of aℓ+1a_{\ell+1} fine blocks, truncating the final batches. Divisibility ensures the partitions are nested. Every block contains at most KℓK_\ell jobs of J′′J'', and the numbers of blocks and superblocks are at most 2b0/aℓ2b_0/a_\ell and 2b0/aℓ+12b_0/a_{\ell+1}, respectively.

Fix an execution of a job in J′′J''. If it is ineligible at level ℓ\ell, 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-ℓ\ell block, hence inside the window; the execution is eligible. At every coarser level, the block containing the execution contains its level-ℓ\ell 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 QQ candidates gives a level for which deletion of all ineligible executions loses at most δ∣J′′∣\delta|J^{\prime\prime}|. Its remaining schedule J′J^\prime satisfies ∣J′∣≥(1−δ)2OPT≥(1−2δ)OPT|J^\prime| \ge(1-\delta)^2\mathrm{OPT} \ge(1-2\delta)\mathrm{OPT}. Furthermore (17) gives

b02δ≤32δτ3OPT≤(1−2δ)OPT≤∣J′∣.\frac{b_0}{2\delta} \le\frac{3}{2\delta\tau^3}\mathrm{OPT} \le(1-2\delta)\mathrm{OPT} \le|J^\prime|.

Since aℓ≥4a_\ell\ge4, the chosen level satisfies

∣B∣≤2b0aℓ≤b02≤δ∣J′∣,KℓD(Kℓ)∣S∣≤2KℓD(Kℓ)b0aℓ+1≤δ2b02≤δ3∣J′∣.|\mathcal{B}| \le\frac{2b_0}{a_\ell} \le\frac{b_0}{2} \le\delta|J^\prime|,\qquad K_\ell D(K_\ell)|S| \le\frac{2K_\ell D(K_\ell)b_0}{a_{\ell+1}} \le\frac{\delta^2 b_0}{2} \le\delta^3 |J^\prime|.

Output all QQ candidates; the schedules J′′J^{\prime\prime} and J′J^\prime 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 nn-vertex planar graph has a vertex separator of size at most 8n\sqrt{8n} whose deletion leaves components of size at most 2n/32n/3. 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 PP be a planar graph on pp vertices and let M≥1M \ge1 be an integer. In polynomial time one can find a set Z⊆V(P)Z \subseteq V(P) with

∣Z∣≤35pM|Z| \le\frac{35p}{\sqrt{M}}

such that every component of P−ZP-Z has at most MM vertices.

Proof. First consider a connected planar graph on nn vertices. Apply the planar separator theorem once. If a remaining component has more than n/2n/2 vertices, it is unique; its size is at most 2n/32n/3. Apply the theorem again to that component. Every component resulting from the second application has at most 4n/94n/9 vertices. Thus the union of the two separators is a half-balanced separator, and its size is at most

8n+8(2n/3)<10n.\sqrt{8n}+\sqrt{8(2n/3)}<10\sqrt{n}.

If no second application is needed, the same bound holds.

Apply this half-balanced separation recursively to every component with more than MM vertices. Charge the deletion of at most 10u10\sqrt{u} vertices from a processed uu-vertex component evenly to its uu vertices, at rate 10/u10/\sqrt{u}. 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 MM, we bound the total charge to the fixed vertex by

10M∑i=0∞2−i/2=10(1−2−1/2)M<35M.\frac{10}{\sqrt{M}}\sum_{i=0}^{\infty}2^{-i/2} =\frac{10}{(1-2^{-1/2})\sqrt{M}}<\frac{35}{\sqrt{M}}.

Summing over the original vertices bounds the total number deleted. The recursion has at most pp nonempty leaves and polynomially many calls. Applying the construction independently to the initial components handles disconnected graphs. □\square

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 κ≥0\kappa\ge0, put

c(κ)=1+2κ(κ+1).c(\kappa) = 1 + 2\kappa(\kappa+ 1).

Lemma B.2 (Two-page separation). Let b≥0b \ge0, m≥1m \ge1, and κ≥0\kappa\ge0 be integers, and let G0,G1G_0, G_1 be simple graphs on the same bb cyclically ordered vertices. Suppose that, within each graph, every edge crosses at most κ\kappa other edges. Suppose also that every connected component of G0G_0 has at most mm vertices. For every integer M≥1M \ge1, one can delete a union of whole G0G_0-components, containing at most

140c(κ)mbM\frac{140c(\kappa)mb}{\sqrt{M}}

vertices, so that every remaining component of G0∪G1G_0 \cup G_1 has at most MM vertices. The construction takes polynomial time.

Proof. A planar representation of the two families. Draw G0G_0 and G1G_1 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 κ\kappa, so a greedy coloring uses at most κ+1\kappa+ 1 colors. Edges of one color give a simple outerplanar graph on the bb original vertices, with at most 2b2b edges. Consequently each hemisphere has at most 2(κ+1)b2(\kappa+ 1)b edges and at most κ(κ+1)b\kappa(\kappa+ 1)b crossings. The planarization PP, obtained by introducing one vertex per crossing, has at most c(κ)bc(\kappa)b vertices. Parallel edges in PP may be suppressed, since they do not change its vertex separators or its connected components.

Deleting whole old components. Apply Lemma B.1 to PP. 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 G0G_0-components meeting this set. Since each such component has at most mm vertices, the number of original vertices deleted is at most 140c(κ)mb/M140c(\kappa)mb/\sqrt{M}.

Why the surviving union is small. For every surviving original edge, its subdivided path in PP 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 MM planar vertices, and hence at most MM 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 MM be the number of machines and OPTM\mathrm{OPT}_M the optimum. We use a common time partition for all machines. For bounded MM, each block configuration records a feasible schedule on all MM machines, and each sampled slot retains its machine label. For sufficiently large MM, 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 MM. We extend Lemma 2.1 to MM identical machines, with a cap KK on the total number of jobs in a block across all machines. Its constants may depend on MM. The block–superblock partition is common to all machines. Write OPT⁡M\operatorname{OPT}_{M} for the optimum on MM machines.

Lemma C.1. For every fixed positive integer MM and every prescribed computable integer-valued function D(K)≥1D(K) \ge1 depending only on KK and δ\delta, a deterministic algorithm either solves the MM-machine instance exactly or constructs Q=δ−1Q = \delta^{-1} candidate block–superblock partitions, with caps depending only on δ\delta, MM, and DD. At least one candidate admits an eligible MM-machine schedule J′J' with at most its cap KK jobs per block and

∣J′∣≥(1−2δ)OPT⁡M,∣B∣≤δ∣J′∣,KD(K)∣S∣≤δ3∣J′∣.|J'| \ge(1-2\delta)\operatorname{OPT}_{M}, \qquad|\mathcal{B}| \le\delta|J'|, \qquad KD(K)|\mathcal{S}| \le\delta^{3}|J'|.

The algorithm runs in nOδ,M(1)poly⁡(N)n^{O_{\delta,M}(1)}\operatorname{poly}(N) time, where the hidden constant may depend on DD.

Proof. Run the greedy refinement of Appendix § 6 with

τ=6MQ,Li=τi+2,K0=ττ+3.\tau= 6MQ, \qquad L_i = \tau^{i+2}, \qquad K_0 = \tau^{\tau+3}.

Each invocation of Greedy⁡(B,E)\operatorname{Greedy}(B,E) still constructs a one-machine schedule, with the same fresh working copy of EE and the same iteration-level reset and commitment rules. Thus the sets JiJ_i remain nested, each JiJ_i has a feasible one-machine schedule, and the stopping iteration is at most τ+1\tau+1.

The charging observation in that appendix now has multiplicity at most MM. Indeed, restrict an MM-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 MM machines gives the claim. Consequently, inside any block after iteration jj, at most 2MLj2ML_j scheduled identities belong to RjR_j. In a kept child, all these identities were unselected and charge to at most LjL_j completions with multiplicity at most MM. In an unkept parent, at most LjL_j identities belong to its tentative greedy schedule; all other identities charge to its at most LjL_j completions. This gives (M+1)Lj≤2MLj(M+1)L_j \le2ML_j. The same bounds persist in finer blocks.

The number of cuts is at most

∑j≥1∣Jj∣Lj≤2OPT⁡Mτ3.\sum_{j \ge1} \frac{|J_j|}{L_j} \le\frac{2\operatorname{OPT}_{M}}{\tau^3}.

Deleting every optimal execution that crosses a cut loses at most 2MOPT⁡M/τ32M\operatorname{OPT}_{M}/\tau^3 jobs, because at most one execution on each machine crosses a cut. Let ii be the stopping iteration. Remove all identities in Ji−1J_{i-1}, clear all machines inside every kept parent of iteration ii, and insert its one-machine greedy schedule on the first machine. The deletion of Ji−1J_{i-1} and insertion of JiJ_i have net loss at most OPT⁡M/τ\operatorname{OPT}_{M}/\tau. After deleting Ji−1J_{i-1}, each kept parent contains at most

2M∑j<iLj≤4MLiτ2M\sum_{j<i} L_j \le\frac{4ML_i}{\tau}

remaining jobs. There are at most OPT⁡M/Li\operatorname{OPT}_{M}/L_i kept parents, so clearing them loses at most 4MOPT⁡M/τ4M\operatorname{OPT}_{M}/\tau jobs. The resulting aligned schedule J′′J'' satisfies

∣J′′∣≥(1−2Mτ3−1+4Mτ)OPT⁡M≥(1−6Mτ)OPT⁡M=(1−δ)OPT⁡M.|J''| \ge\left(1-\frac{2M}{\tau^3}-\frac{1+4M}{\tau}\right)\operatorname{OPT}_{M} \ge\left(1-\frac{6M}{\tau}\right)\operatorname{OPT}_{M} = (1-\delta)\operatorname{OPT}_{M}.

Every kept child contains at most LiL_i inserted jobs, and every unkept parent contains at most 4MLi/τ≤Li4ML_i/\tau\le L_i remaining jobs. Thus the cap is K0K_0. If OPT⁡M≥τ3\operatorname{OPT}_{M} \ge\tau^3, the number b0b_0 of fine blocks satisfies b0≤3OPTM/τ3b_0 \le3\mathrm{OPT}_M/\tau^3. The construction has O(n)O(n) blocks and uses binary arithmetic on the original endpoints.

Apply the nested grouping scales from Appendix § 6 with this value of K0K_0 and the same Q=δ−1Q=\delta^{-1}. To handle the small-optimum branch, let R=⌈max⁡{τ3,2K0αQ+1}⌉R=\lceil\max\{\tau^3,2K_0\alpha_{Q+1}\}\rceil and enumerate job subsets of size at most R+1R+1, 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 R+1R+1 exists, this enumeration finds an optimum. Otherwise the lower bound on b0b_0 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 QQ levels. A good level has an eligible MM-machine schedule J′J' with

∣J′∣≥(1−2δ)OPTM,∣B∣≤δ∣J′∣,KD(K)∣S∣≤δ3∣J′∣.|J'| \ge(1-2\delta)\mathrm{OPT}_M,\qquad|B| \le\delta|J'|,\qquad KD(K)|S| \le\delta^3|J'|.

Here KK bounds the total number of jobs per block. The last two inequalities follow from the same calculation as in the single-machine case, since τ≥6Q\tau\ge6Q. For fixed MM the running time is nOδ,M(1)poly⁡(N)n^{O_{\delta,M}(1)}\operatorname{poly}(N).

Configurations and rounding on a fixed number of machines

Fix a constant number MM 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 KK bounds the total number of jobs in a block, summed over the MM machines.

For each block BB, let CBC_B contain the eligible job sets of size at most KK that admit a schedule on the MM machines inside BB. 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 MM 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 BB. The test succeeds for some assignment and orders exactly when the set is feasible. Since MM and KK are constants, this takes nO(K)poly⁡(N)n^{O(K)}\operatorname{poly}(N) time per block.

The distributions xB,⋅x_{B,\cdot} and μU\mu_U, their consistency constraints, and the job constraints are the same as in § 2. Every tuple in TUT_U 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 OPT=OPTM\mathrm{OPT}=\mathrm{OPT}_M.

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 aja_j, bjb_j, cjc_j, hjh_j, qjq_j and the reservations in (6) have the same interpretation. A group of at most mm blocks contains at most β=Km\beta=Km 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 [s,t)[s,t) runs on that slot’s machine from max⁡{s,rj}\max\{s,r_j\} for pjp_j 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 MM 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 β\beta. 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 F′−W+H−4δFF' - W + H - 4\delta F.

Combining the three scores as in § 5, and using the same finite-bit implementation, gives an expected cardinality of at least (11/12−8δ)OPTM(11/12 - 8\delta)\mathrm{OPT}_M. With the choice of δ\delta made there, this is at least OPTM/(12/11+ε)\mathrm{OPT}_M/(12/11 + \varepsilon).

An arbitrary number of machines

Im, Li, and Moseley [4] give, for every fixed η>0\eta> 0, a polynomial-time algorithm for unweighted throughput maximization on MM identical machines whose expected retained fraction is at least

1−Clog⁡MM−η,1 - C\sqrt{\frac{\log M}{M}} - \eta,

for an absolute constant C≥1C \ge1 and M≥2M \ge2, where log⁡\log 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 η=1/32\eta= 1/32 and the absolute integer

M⋆=max⁡{2,⌈(32C)4⌉}.M_\star= \max\{2, \lceil(32C)^4\rceil\}.

For M≥M⋆M \ge M_\star, the inequality log⁡M≤M\log M \le\sqrt{M} gives

Clog⁡MM≤CM−1/4≤132.C\sqrt{\frac{\log M}{M}} \le CM^{-1/4} \le\frac{1}{32}.

The algorithm of Im, Li, and Moseley therefore returns a feasible schedule with expected cardinality at least

1516OPTM≥1112OPTM≥OPTM12/11+ε.\frac{15}{16}\mathrm{OPT}_M \ge\frac{11}{12}\mathrm{OPT}_M \ge\frac{\mathrm{OPT}_M}{12/11+\varepsilon}.

For M<M⋆M < M_\star, 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 nn by nn, since any schedule of at most nn jobs uses at most nn machines. Instances with at most one job are solved directly. For M<M⋆M < M_\star, the preprocessing parameters satisfy

τ=6MQ=O(Q),K0=(6MQ)6MQ+3,log⁡2K0=O(Qlog⁡Q),\tau= 6MQ = O(Q), \qquad K_0 = (6MQ)^{6MQ+3}, \qquad\log_2 K_0 = O(Q\log Q),

uniformly over this range of MM. The bound D(K)≤C07K42δ−168D(K) \le C_0^7K^{42\delta-168} and the recurrence for the nested scales are unchanged. The proof of Proposition 5.1 therefore gives the same bound

n22O(1/εˉ)poly⁡(N),εˉ=min⁡{ε,1}.n^{2^{2^{O(1/\bar{\varepsilon})}}}\operatorname{poly}(N), \qquad\bar{\varepsilon} = \min\{\varepsilon,1\}.

The additional factor MKM^K for machine assignments is absorbed into nO(K)n^{O(K)} because M<M⋆M < M_\star and n≥2n \ge2. For M≥M⋆M \ge M_\star, the algorithm invoked at the fixed accuracy η=1/32\eta= 1/32 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. [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. [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
  3. [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
  4. [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
  5. [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
  6. [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.
  7. [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

Paper details

vlnc:W_qywyzz26
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 6 Pro

View statement
Looking for related papers…
Contents