XSci

Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization

Weitian Tong, Yao Xu

Submitted by Weitian Tong

Published November 5, 2026 · Version v1, November 5, 2026 · DOI 10.66977/xsci.2611.000k

Theoretical Computer Science, Algorithms, Operations Management

Abstract

We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed ε>0, we give randomized algorithms with expected approximation ratios 17/13+ε in polynomial time and 21/17+ε in pseudopolynomial time. These improve the respective 4/3+ε and 5/4+ε guarantees of Armbruster, Grandoni, Tinguely, and Wiese [STOC'26]. Both results hold for an arbitrary number of identical machines.

Our algorithms build on their configuration-LP and matching framework, which partitions time into blocks. For a job whose window meets multiple blocks, its boundary blocks are the first and last such blocks. Crossing boundary pairs, whose endpoints strictly interleave, permit additional assignments to sampled execution slots, while a noncrossing family can be coordinated using consistent joint distributions on at most three blocks. The exchange analysis accounts for fractional job assignments that must be erased before inserting an additional job. For the pseudopolynomial implementation, we project configurations onto selected job identities and use separate configuration distributions with common placement marginals. This retains efficient pricing while enforcing the correlations needed for coordination.

View PDF

Review reports

xPeerd (AI review)

November 5, 2026

AI Review (xPeerd — DAReview)

Summary

This manuscript studies unweighted non-preemptive throughput maximization on identical machines and claims improved randomized approximation ratios of 17/13 + ε in polynomial time and 21/17 + ε in pseudopolynomial time for any fixed ε > 0. The paper is clearly positioned against recent prior work and explains its main technical contributions in terms of stronger matching analysis, crossing exchanges, and coordinated sampling over boundary blocks. The abstract and Theorem 1.1 state the claimed advances precisely, and the manuscript generally maintains a coherent theoretical arc from structural decomposition to LP relaxation, rounding, and implementation .

Its main strengths are a well-scoped problem statement, explicit theorem-level contributions, and a comparatively transparent roadmap linking the two-output rounding argument to the final approximation guarantees . The presentation also includes implementation details for both polynomial and pseudopolynomial variants, which is important for reproducibility in approximation-algorithm research .

The main weaknesses are not obvious logical contradictions, but rather risks in verification burden, dependence on imported constructions from [AGTW26], dense notation, and several places where key proof intuitions are compressed into highly technical statements whose correctness is difficult to audit from exposition alone. The manuscript appears mathematically coherent, but it would benefit from stronger self-contained explanation, clearer separation of inherited versus novel proof ingredients, and more explicit guidance for readers verifying the claimed approximation improvements.

Potential Major Revisions

  1. Burden of verification remains very high because the novelty depends on subtle improvements over recent prior work, but the manuscript often compresses the exact locus of improvement.

The manuscript states that it improves the STOC’26 guarantees from “4/3 + ε and 5/4 + ε” to “17/13 + ε in polynomial time and 21/17 + ε in pseudopolynomial time” . It further says, “Our algorithms build on their configuration-LP and matching framework” and that the improvement “combines a stronger analysis of maximum job–slot matching through crossing exchanges with coordinated sampling for a noncrossing family of boundary edges” . This is plausible and coherent, but the manuscript should do more to isolate exactly which proof steps are new, which constants improve, and which assumptions are inherited unchanged. Table 1 helps, but it remains too compressed for such a technically fine-grained advance .

A revision should include a self-contained “delta from [AGTW26]” subsection early in the introduction, identifying:

  • the exact inherited lemmas or frameworks,
  • the exact new lemmas,
  • the exact inequality where 4/3 becomes 17/13,
  • the exact inequality where 5/4 becomes 21/17.

Without that, expert readers must reverse-engineer the novelty.

  1. Some central guarantees are asserted clearly, but the exposition does not sufficiently lower the risk of hidden proof gaps in the combined rounding argument.

The visual roadmap says, “Computing both schedules avoids having to predict which is better,” and Theorem 3.5 claims “E[max{A×, Akeep}] ≥ L + 13G/17 − 8ηF” . This is elegant, but because the contribution relies on balancing opposite dependencies on D and ν, the argument is delicate. The proof text says the convex weights “16/17 and 1/17” cancel these terms because “16(D/4 + ν/16) = 4D + ν” . That algebra is concise, but the manuscript should add a short prose explanation of why these are the natural balancing weights and whether they are optimal or simply sufficient.

This matters because the claimed improvement is ratio-sensitive. If the bound is sharp only under a particular decomposition of losses, the reader should be told that explicitly.

  1. Reproducibility of the theoretical implementation would be improved by more explicit algorithmic pseudocode and complexity bookkeeping.

The manuscript does provide important implementation detail. For example, in Section 4.1 it explains how configurations are enumerated, feasibility is tested, and stored schedules are produced, noting that “This test uses binary arithmetic and produces the stored schedules needed for rounding” . For exact pricing with required jobs, it also presents a dynamic programming formulation and use of perfect hash families . However, the implementation story remains spread across several sections and appendices.

A major revision should consolidate the following into one algorithmic appendix:

  • complete pseudocode for the polynomial-time implementation,
  • complete pseudocode for the pseudopolynomial implementation,
  • explicit input/output conventions,
  • exact randomization steps,
  • explicit statement of what is stored at each stage,
  • complexity of each subroutine in terms of n, T, m, K, and ε.

At present, the implementation appears principled, but not maximally auditable.

  1. The manuscript is coherent within a recognized approximation-algorithms paradigm, but the dependency on external results is strong enough that some proof interfaces should be restated more formally.

The paper repeatedly builds on [AGTW26], [COR06], and [ILM20], and some claims are only understandable if the reader already knows those constructions. For instance, the manuscript says, “The construction of [AGTW26, Lemmas 4 and 27] gives a partition B0 into elementary blocks and an aligned reference schedule O′′” , and later says “The pseudopolynomial bound additionally uses the complementary global-job rounding of [AGTW26]” . This is acceptable in principle, but high-stakes claims should not hinge on opaque imports.

The authors should restate the exact imported assumptions and outputs of prior lemmas in theorem-box form, so a reader can verify the logical dependencies without consulting another manuscript.

  1. The paper would benefit from stronger discussion of limits, failure modes, and why the approach does not yet reach PTAS territory.

The related work section correctly notes that “Whether it admits a polynomial-time approximation scheme (PTAS) ... remains open” . The paper also identifies future directions such as “analyze exchanges among larger sets of jobs with crossing boundary edges” and “coordinate crossing boundary families whose graph on blocks admits a tree decomposition” . However, there is still little explicit explanation of the bottleneck preventing further improvement.

A stronger limitations paragraph should explain:

  • which loss term currently dominates,
  • why the current coordination only handles noncrossing families,
  • whether the 1/4 threshold is intrinsic or technical,
  • whether the projected consistency method plausibly scales to stronger guarantees.

This would sharpen the scientific contribution.

  1. Integrity and fraud-screen assessment

I do not see overt paper-mill markers, fabricated experimental data, or incoherent scientific framing. The manuscript fits a recognized theoretical computer science paradigm, uses field-appropriate formalism, and includes a coherent reference structure . The declared absence of datasets is consistent with the paper’s theoretical nature, and the AI-assistance declaration is unusually explicit: “We used OpenAI ChatGPT to assist with preparing computational checks, drafting and revising the manuscript” . That declaration is not itself problematic, but because the paper’s contribution is proof-sensitive, reviewers may reasonably expect especially careful verification of novel arguments. I therefore do not flag likely fraud, but I do flag elevated verification sensitivity.

Potential Minor Revisions

  1. Terminological consistency

The title uses “Non-Preemptive” while the introduction uses “Nonpreemptive throughput maximization” . Choose one style consistently throughout the title, abstract, headings, and body.

  1. Clarify expectation language

The introduction defines an expected ρ-approximation as one returning a feasible schedule whose “expected throughput is at least OPT/ρ” . Later table and figure captions discuss guarantees “in expectation” in more informal language . Consider a brief notation note distinguishing:

  • expected output size,
  • expected approximation ratio,
  • guarantee on the maximum of two sampled outputs.
  1. Improve local readability of dense notation

Statements such as “Write xB = (xB,C)C∈C(B) for the distribution at block B” and the introduction of F, L, G, Z, W, D, ν, P, Q, and Jmiss produce a high symbol density . A compact notation table near the start of Section 3 would materially improve readability.

  1. Add one running example

The manuscript includes figures and roadmap summaries, but a single running toy instance through:

  • block formation,
  • local/global job distinction,
  • crossing versus noncrossing boundaries,
  • independent sampling,
  • coordinated output, would reduce cognitive load. Figure 8 is helpful conceptually, but not enough for first-pass comprehension .
  1. Tighten exposition around projected consistency

The line “Projected consistency enforces correlations; color coding with required jobs handles one additional subset term per configuration copy” is informative but terse . Readers would benefit from one short paragraph giving intuition for why storing only tracked identities is enough.

  1. Formatting and typography

There are visible OCR-style or encoding artifacts in extracted formula regions, for example unusual glyph renderings around summations and inequalities in the retrieved text . If these artifacts are present in the actual PDF rather than extraction only, they should be corrected. Also ensure consistent spacing around citations such as “[BNBYF+ 01]” and similar entries in the references and body .

  1. Reference-update precision

The manuscript cites “[AGTW26] ... Full version: https://arxiv.org/abs/2603.29451v1” . If a later version exists and is the one actually used, update to the most stable citable version.

  1. AI content analysis

The manuscript explicitly discloses AI assistance: “We used OpenAI ChatGPT to assist with preparing computational checks, drafting and revising the manuscript” . Based on style uniformity, polished transition language, and this direct disclosure, I estimate a moderate probability of AI-assisted drafting in some expository sections, especially summary prose and roadmap language. Estimated AI-generated or AI-assisted prose content: 15–30%.

Highlighted likely AI-assisted sections:

  • Abstract, especially the compact high-level framing of contributions
  • The roadmap-style explanatory text in Figure 8 / Appendix C
  • Statements and Declarations language

Assessed epistemic impact: Low to moderate. Because the paper is a theoretical manuscript, epistemic risk depends far more on proof correctness than prose origin. The disclosed AI use does not by itself weaken the contribution, but it strengthens the need for rigorous human verification of all proofs, computational checks, and references.

Recommendations

  1. Add a dedicated “What is new relative to [AGTW26]?” subsection near the end of the introduction.
  2. Insert a notation table before Section 3.
  3. Expand the proof intuition around Theorem 3.5, especially the choice of convex weights 16/17 and 1/17.
  4. Restate all imported prior-work lemmas in self-contained interface form.
  5. Consolidate the polynomial and pseudopolynomial implementations into auditable pseudocode.
  6. Add a small worked example showing boundary blocks, good/bad jobs, crossing pairs, and coordinated sampling.
  7. Expand the limitations discussion to explain what currently blocks further ratio improvement.
  8. Carefully proofread notation/style consistency and check for any PDF rendering artifacts.
  9. Given the disclosed AI assistance, perform and document an additional internal proof audit before submission.

Overall, my assessment is favorable on technical ambition and plausibility, but I think the manuscript still needs revision before it is optimally review-ready. The main issue is not obvious invalidity; it is that the exposition does not yet make the claimed improvement easy enough to verify relative to the delicacy of the proof contributions.

XSci (AI review)

November 5, 2026

Summary

The paper studies unweighted non-preemptive throughput maximization: given n jobs with integer processing times, release times and deadlines and m identical machines, schedule a maximum-cardinality subset so that each selected job runs continuously inside its window. The authors inherit the framework of [AGTW26] — blocks and superblocks, a configuration LP over bounded-size configurations, independent sampling, and maximum job-slot matching — and add two ingredients that exploit the relative order of jobs' boundary blocks. First, when two jobs' boundary pairs strictly interleave, a duplicate selection of the longer job can be converted into an execution of the shorter one (Lemma 3.2); second, the configuration LP is strengthened by consistent joint distributions on every set of at most three blocks, so that a noncrossing family of jobs can be sampled with none selected at both of its boundaries (Lemma 2.2). Combining the two outputs with weights 16/17 and 1/17 cancels both the aggregate boundary deficit D and the size ν of the chosen crossing matching, giving E[max{A_×, A_keep}] ≥ L + (13/17)G − 8ηF (Theorem 3.5). With the complementary global-job rounding of [AGTW26], this yields expected ratios 17/13 + ε in polynomial time and 21/17 + ε in pseudopolynomial time (Theorem 1.1).

Contribution and Significance

The core contribution is a pair of complementary improvements to the rounding of the configuration LP, together with the observation that they can be traded against each other at a fixed rate. Lemma 3.2 shows that a crossing pair of boundary edges yields an expected gain of at least (a_j b_j)(a_k b_k) for the maximum job-slot matching; Lemma 2.2 shows that a noncrossing family can be sampled with no boundary duplicate using only local consistency on triples of blocks. The combination in Section 3.4 is the real insight: the same maximal crossing matching X that supplies the gain ν/16 to the first output is exactly what the second output pays for, and D enters the two bounds with opposite signs, so the fixed weights annihilate both. This matters because it shows that the boundary-collision loss of G/4, which has been the binding term in this framework, is not intrinsic — it can be attacked by exploiting duplicates or by preventing them, and a convex combination beats either alone.

Relative to [AGTW26], from which the blocks, superblocks, configuration LP, job-slot matching, size grouping, color-coding pricing and third output are taken (Table 1 is admirably honest about this), what is genuinely new is the crossing exchange, the three-block lift, and the projected-consistency machinery of Sections 4.2–4.4 that makes the lift implementable when K = Θ(log T). The quantitative advance is nevertheless small: the retained global fraction moves from 3/4 to 13/17, that is by G/68, and the pseudopolynomial guarantee from 4F/5 to 17F/21, by F/105. No barrier moves — APX-hardness remains open, and no integrality gap is given for the new relaxation. The durable value here is more likely the technique, in particular the pseudopolynomial implementation of an LP lift whose variables are only implicitly represented, than the constants.

Strengths

  • The cancellation in Theorem 3.5 is elegant and robust: because 16(D/4 + ν/16) = 4D + ν, the guarantee needs neither a maximum crossing matching nor any control on the shape of the boundary marginals.
  • Lemma 3.2 is careful exactly where this kind of argument usually fails. The pointwise bound f_j ≤ (z_j/D_j)·1{j absent at both boundaries} from Lemma 3.1 is what pays for erasing the inserted job's interior fractional assignment, and the proof verifies simultaneity — distinct freed slots, boundary slots unused by f, disjoint job identities — instead of asserting it.
  • Lemma 2.2 reduces "never select a job at both boundaries" to conditional sampling along a polygon triangulation, and Section 2.3 is careful to put all triples into the LP so that the triangulation may be chosen after the LP is solved.
  • Section 4.3 solves a real difficulty: the rational piecewise-linear surrogate for the quadratic penalty bounds the number of reoptimizations by O(n/η²) (Lemma 4.1), and the gap between the tracking threshold 1/8 and the good-job threshold 1/4 converts the stopping rule into |J_miss| ≤ ηF, precisely the hypothesis Theorem 3.5 requires.
  • Appendix B reproves the imported complementary rounding in full, including the long-assignment bound 4(⌊log₂T⌋+1)/η⁴ ≤ Δ and the Chernoff estimate, rather than citing it.

Recommendation

Major Revision for Algorithmica. The algorithmic ideas are new and the analysis reproduces everywhere I was able to check it, so the contribution is of the kind this journal publishes. Two things stand in the way. The structural lemma on which every later constant depends is stated with a parameter that its own proof contradicts, and its imported hypotheses are not stated, so the main theorem is not independently verifiable from this manuscript. And because the paper competes essentially on the size of two constants, it needs to say where its analysis is tight; as it stands a reader cannot tell whether 17/13 is the limit of the construction or an artifact of a few loose estimates.

Major Concerns

  1. Lemma 2.1 is not what Appendix A proves, and its density bound fails with the stated constant (Section 2.1; Appendix A). Lemma 2.1 defines Γ = 2K₀/η. Appendix A instead states "Recall that Γ = 2K₀/η⁷", and uses that value in the display K_ℓ|S_ℓ| ≤ K₀b/Γ = η⁷b/2, from which it concludes K_{ℓ*}|S_{ℓ*}|/η⁸ ≤ b/(2η) ≤ |O′|. With the lemma's Γ = 2K₀/η the same computation gives K_ℓ|S_ℓ| ≤ ηb/2 and hence only K_{ℓ*}|S_{ℓ*}|/η⁸ ≤ b/(2η⁷), which does not follow from |O′| ≥ mb/(2η) unless m ≥ η⁻⁶. Lemma 2.1(d) therefore does not hold as stated, and that bound is the source of the LP constraint F ≥ K|S|/η⁸ used in Lemma 3.1 and in the step 5K|S|/η⁶ ≤ 5η²F of Lemma 3.2. Since Γ also determines H = ⌈5K₀ΔΓ^q⌉ and K ≤ ΔΓ^q, the correction must be carried through the statement of Lemma 2.1, Algorithm 2, and the running-time bounds.

    Compounding this, Appendix A takes from [AGTW26, Lemmas 4 and 27] the elementary partition B₀ and the reference schedule O″ with its three properties, and the threshold "H ≥ (6m/η)³ … required by the imported construction", without stating any of them. Since every later constant is calibrated against Lemma 2.1, the imported statement should be reproduced and the derived quantities recomputed, so that a reader can certify Theorem 1.1 from this paper alone.

  2. The improvement is never placed against the limits of the approach (Sections 3.3, 3.4, 5). The paper's claim on the reader's attention is the move from 3/4 to 13/17 of G and from 4/5 to 17/21 of F, yet nothing in the manuscript indicates where its bounds bind. Several steps are visibly lossy: the charge min{a_j, b_j} ≤ 4e_j for bad jobs in Lemma 3.3; the flat loss of one unit per matched pair in the same lemma; the term 9e_je_k discarded in Lemma 3.4; the use of a maximal rather than a maximum crossing matching; and the hand-chosen threshold 1/4 separating good from bad jobs. An instance family on which E[max{A_×, A_keep}] is (13/17)F + o(F), or an optimization over the threshold and the convex weights establishing that 13/17 is the best the two bounds give, would settle whether this is a technique with headroom or a one-off ε — the distinction that determines the value of the paper.

Minor Comments

  1. Section 1 defines y_{j,B} := Σ_{C∈C(B)} x_{B,C} without the restriction j ∈ C, which Section 2.2 states correctly.
  2. "Spieksha's greedy algorithm [Spi99]" (Section 1): the author's name is Spieksma, as the reference list has it.
  3. The assertion that "[t]he original LP does not guarantee that its block distributions extend to joint distributions satisfying all these requirements" (Section 1.1) is never substantiated; the table in Section 2.3 exhibits two mutually inconsistent distributions, not a configuration-LP solution admitting no consistent extension, and Sections 4.2–4.4 exist solely to implement the strengthening.
  4. With Γ = 2K₀/η⁷ and q = 1/η, the exponent in the n^{O(K)} enumeration of Section 4.1 is a tower in 1/ε; a remark on the actual ε-dependence is warranted in a paper that competes on constants.
  5. Section 4.4 would be easier to check if the pricing cost were given component-wise — 2^κ(T+1) DP entries, m^κ machine assignments, 2^{8K} tracked subsets — rather than only as (2m)^{O(K)}poly(n,T,N,Λ).
  6. In the proof of Lemma 3.3, "If a missed job is already matched, this estimate only counts its loss twice" should say that the bound double counts such a job, which is why it remains valid.
  7. The caption of Figure 8 (Appendix C) is a glossary of local, global and good jobs rather than a legend for the roadmap flowchart it accompanies.
  8. Since the guarantees hold only in expectation, a sentence on repetition or derandomization — how many runs suffice to attain the ratio with high probability — would help anyone wanting to use the algorithm.
  9. The abstract would calibrate the reader better if, alongside 4/3 → 17/13, it reported the quantity actually improved: the retained fraction of the global mass, from 3/4 to 13/17.