PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Weitian Tong, Yao Xu

arXiv:2610.34656v1cs.DS

TL;DR

Unweighted nonpreemptive throughput maximization asks for a maximum-cardinality feasible subset of jobs with time windows on identical machines. This paper improves prior approximation guarantees by combining boundary-aware matching with coordinated sampling. It achieves expected ratios of 17/13 + ε in polynomial time and 21/17 + ε in pseudopolynomial time.

  • Problem

    The problem is to schedule a maximum-cardinality feasible subset of jobs with processing times, release times, and deadlines on identical machines.

    Source: §1 · p. 2

  • Method

    The algorithms build on a configuration-LP and matching framework, exploiting crossing boundary pairs and coordinating sampling with consistent joint distributions on up to three blocks.

    Source: §1 · p. 4, §1.1 · p. 4

  • Results

    17/13 + ε in polynomial time and 21/17 + ε in pseudopolynomial time improve the respective 4/3 + ε and 5/4 + ε expected approximation ratios for any number of identical machines.

    Source: §1 · p. 2, §5 · p. 27

  • Takeaways & Limitations

    The improved guarantees combine matching that exploits duplicate selections with coordinated rounding that avoids some duplicates.

    Source: §1 · p. 4, §5 · p. 27

    The coordinated construction preserves distributions only for the block sets it uses, not every prescribed pair or triple distribution.

    Source: §2.3 · p. 14

Abstract

from arXiv · show

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 $\varepsilon>0$, we give randomized algorithms with expected approximation ratios $17/13+\varepsilon$ in polynomial time and $21/17+\varepsilon$ in pseudopolynomial time. These improve the respective $4/3+\varepsilon$ and $5/4+\varepsilon$ 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.

1 Introduction

The paper improves approximation guarantees for unweighted nonpreemptive throughput maximization on identical machines by exploiting boundary order in matching and coordinating configuration sampling. Its approach builds on prior block and configuration-LP methods, while the polynomial-time approximation-scheme status of the problem remains open.

1 Introduction

  • Unweighted nonpreemptive throughput maximization selects the largest feasible subset of jobs, but whether it admits a PTAS remains open.Jobs have processing times, release times, and deadlines; schedules execute each selected job continuously within its window without machine overlap.Source: §1 · p. 2, §1.2 · p. 7
  • 17/13 + ε in polynomial time and 21/17 + ε in pseudopolynomial time improve the respective 4/3 + ε and 5/4 + ε guarantees for any number of identical machines.The randomized algorithms always return feasible schedules, and the guarantees hold in expectation.Source: §1 · pp. 2, 4

1.2 Related work

  • Earlier work established the block-and-configuration framework and improved guarantees through matching and individual block assignment, including the 4/3 + ε and 5/4 + ε bounds this paper surpasses.The unweighted problem is strongly NP-hard on one machine, while its PTAS status remains unresolved.Source: §1 · pp. 2–3, §1.2 · p. 7

1.1 Sketch of our approach

  • The prior 4/3 + ε and 5/4 + ε algorithms use block partitions, configuration LPs, and job–slot matching; this paper improves their rounding by exploiting boundary order.Crossing boundary pairs enable additional slot reuse, while coordinated sampling addresses duplicate selections among a noncrossing family.Source: §1 · pp. 3–4, §1.1 · p. 4
  • Crossing exchanges can recover a job missed at both boundaries by assigning it to a duplicate job’s spare slot, after erasing its fractional interior assignments.The pointwise bound on erased fractional mass yields an expected net gain of at least (a_j b_j)(a_k b_k).Source: §1.1 · pp. 4–5
  • Consistent joint distributions on up to three blocks let the algorithm coordinate sampling across a triangulation and avoid duplicate boundary selections for unmatched good jobs.The construction preserves each block’s configuration distribution and extends sampling conditionally across shared block pairs.Source: §1.1 · pp. 5–6, Figure 3 · p. 5
  • For pseudopolynomial implementation, projected consistency tracks selected job identities while separate configuration copies share placement marginals, preserving correlations without explicitly enumerating large configurations.The approach uses at most 2^O(K) projected states per group of up to three blocks and supports efficient pricing.Source: §1.1 · p. 6

2 Partitions and configuration distributions

The framework partitions time into blocks and superblocks, restricts eligible placements, and represents feasible schedules through block configurations. Consistent joint distributions on up to three blocks then support coordinated sampling for noncrossing boundary pairs.

2.1 Blocks, superblocks, and alignment

  • Integer-time preprocessing and candidate partitions yield an aligned reference schedule with bounded block density and eligible placements.Jobs longer than their windows are discarded; integral release and processing times permit shifting executions to integer start times. The construction supplies at most q candidate partitions, one of which has a qualifying reference schedule when OPT ≥ H.Source: §2 · p. 8, §2.1 · p. 9
  • Local jobs use their single block, while global jobs may use boundary blocks and blocks in superblocks fully spanned by their windows.Eligibility constrains the structural construction and relaxation, but the final matching may use other placements feasible in the original instance.Source: §2.1 · pp. 8–9

2.2 Configurations and placement mass

  • A block configuration is a feasible set of at most K eligible jobs scheduled on the machines entirely within that block.The algorithm retains a feasible schedule witnessing each configuration it uses; one distribution over configurations is assigned to each block, with placement marginals defining each job’s fractional mass.Source: §2.2 · p. 10
  • The relaxation separates local and global fractional mass and tracks each global job’s boundary and interior placements, with total mass at most one.Boundary mass and interior mass are disjoint, and interior placement in a superblock is allowed only when the job spans it.Source: §2.2 · p. 10

2.3 Consistency on triples and noncrossing boundaries

  • For a noncrossing family of boundary edges, triangulation organizes conditional sampling so selected jobs are not chosen at both boundary blocks.Each triangle uses a joint distribution on at most three blocks; in the projected version the same guarantee applies when each selected job is tracked at both endpoints.Source: §2.3 · pp. 11, 13
  • Joint distributions on every set of up to three blocks must agree on their shared subsets, while singleton distributions preserve each block’s configuration distribution.This strengthening retains the reference schedule as a feasible solution and prevents inconsistent pairwise choices across triples.Source: §2.3 · pp. 11–12
  • The sampling preserves block and used-triangle distributions, but need not preserve prescribed distributions on other pairs or triples.The relaxation is solved before choosing the noncrossing family, so the selected triangulation determines which joint distributions are preserved.Source: §2.3 · p. 14

3 Rounding the configuration solution

The section rounds a shared configuration solution through two schedules: independent sampling with job–slot matching, and a coordinated boundary sample; the algorithm returns the larger. The rounding combines interior-slot reuse, exchanges for crossing boundaries, and coordinated sampling for noncrossing boundaries.

3.1 Independent sampling and interior matching

  • Independent block samples feed a maximum job–slot matching and an auxiliary fractional matching that recovers global-job mass from interior slots.Within each superblock, jobs are grouped by nonincreasing processing time, so earlier groups’ slots can serve jobs in the next group.Source: §3.1 · pp. 14–16

3.2 Recovering jobs from crossing boundaries

  • For crossing boundary pairs, when the shorter job is absent at both boundaries and the longer appears at both, relocate the longer job and assign the shorter to its freed boundary slot.The exchange deletes old fractional assignments to the shorter job, so its gain is at least 1−fr rather than automatically one.Source: §3.2 · pp. 18–19

3.3 Coordinating a noncrossing family

  • Jointly sample configurations to prevent duplicate boundary appearances for unmatched good jobs with noncrossing boundaries; restrict other global jobs to one more likely boundary.In the projected version, the coordinated family excludes jobs in Jmiss.Source: §3 · p. 14, §3.3 · p. 19

3.4 Combining the two schedules

  • Combining the two schedule guarantees cancels their opposite dependence on D and the crossing-matching size, yielding the theorem guarantee under full consistency and under projected consistency when |Jmiss|≤ηF.The proof combines the bounds using weights 16/17 and 1/17; no independence between the output schedules is needed.Source: §3.4 · p. 20

4 Implementation and approximation guarantees

The implementation combines configuration enumeration for polynomial time with projected consistency and exact pricing for the pseudopolynomial case. Iterative marginal control and complementary rounding complete the guarantees for arbitrary numbers of identical machines.

4.1 The polynomial-time implementation

  • Enumerating eligible job sets, machine assignments, and machine orders yields stored feasible schedules and a polynomial-size consistency LP for the polynomial-time implementation.The LP retains job and density constraints; its selected candidate has objective at least (1 − 2η)OPT.Source: §4.1 · p. 21

4.2 Projected consistency and configuration copies

  • Projected consistency uses separate configuration distributions linked by common placement marginals, with joint distributions on tracked sets across groups of at most three blocks.Tracked sets are carried from successive solutions and remain attached to earlier copies during reoptimization.Source: §4.2 · pp. 21–22, Figure 7 · p. 22

4.3 Controlling changes in the marginals

  • A small quadratic penalty on marginals makes large changes between successive solutions measurably decrease the objective, limiting failed stopping tests to ⌊4n/(βγ)⌋; when OPT ≥ H, largest-terminal-F selection gives F ≥ (1 − 3η)OPT.A rational piecewise-linear approximation enables this property to be obtained using only LPs.Source: §4.3 · pp. 22–23

4.4 Exact pricing with required jobs

  • Color coding and machine-wise dynamic programming exactly price configurations while requiring prescribed tracked-job identities, with total pricing time (2m)^O(K) poly(n, T, N, Λ).Recording maximizing choices also recovers a feasible witness schedule.Source: §4.4 · pp. 24–25

4.5 Completion of the guarantees

  • For pseudopolynomial time, the method selects the largest of matching-based and complementary-rounding schedules; the comparison of their guarantees needs no independence between outputs.The complementary rounding uses the same selected configuration distributions and stored schedules.Source: §4.5 · p. 26
  • For fixed m and ε, the approximation ratios are 17/13 + ε and 21/17 + ε; respective running times, including exact target tests, are n^(O_{m,ε}(1)) poly(N) and (nT)^(O_{m,ε}(1)) poly(N).Source: §4.5 · p. 27
  • For arbitrary machine counts, the algorithm uses the fixed-machine method below a threshold and an existing polynomial-time algorithm above it, retaining both claimed approximation factors.The large-machine algorithm retains at least 1/(1 + ε) of the optimum for the chosen parameter.Source: §4.5 · p. 27

5 Conclusion

The paper improves approximation guarantees for unweighted nonpreemptive throughput maximization on identical machines. It identifies stronger exchange analyses and coordination beyond the current approach as directions for further improvement.

5 Conclusion

  • The algorithms improve [AGTW26]’s ratios from 4/3+ε to 17/13+ε in polynomial time and from 5/4+ε to 21/17+ε in pseudopolynomial time.Both randomized algorithms return feasible schedules and guarantee their approximation ratios in expectation.Source: §5 · p. 27
  • The improvements combine crossing exchanges in maximum job–slot matching with coordinated sampling for a noncrossing family of boundary edges.Using the same selected configuration solution lets the matching and coordinated-rounding guarantees be combined.Source: §5 · p. 27
  • Future work could analyze exchanges among larger sets of jobs or coordinate crossing boundary families whose block graph has a bounded-width tree decomposition.The former aims to account for conflicts and fractional interior assignments that must be erased; the latter would use consistent joint distributions on decomposition bags.Source: §5 · pp. 27–28

Statements and Declarations

The authors report no relevant competing interests, identify their individual contributions, state that no datasets were generated or analyzed, and disclose ChatGPT assistance.

Statements and Declarations

  • The authors disclose no relevant financial or non-financial competing interests.Source: Statements and Declarations · p. 28
  • Tong contributed across conceptualization, analysis, methodology, project administration, supervision, validation, and writing, while Xu contributed to analysis, methodology, validation, and writing.Source: Statements and Declarations · p. 28
  • No datasets were generated or analyzed, and the authors used ChatGPT for computational checks and manuscript drafting and revision.The authors state that they independently verified the mathematical claims, proofs, computations, and references and take responsibility for the final contents.Source: Statements and Declarations · p. 28

A The dense partition specialization

This appendix specializes a dense partition construction by forming block and superblock partitions across multiple scales. One level has few ineligible reference executions, yielding an aligned, eligible schedule close in size to the optimum.

A The dense partition specialization

  • The partition lemma modifies the merging step of [AGTW26, Lemmas 6 and 28], while retaining the initial partition and using a larger Γ for the required superblock density.Source: A The dense partition specialization · p. 28
  • The fixed-machine reduction places machine-specific job windows in consecutive copies of the time horizon, using binary arithmetic rather than enumerating start times.The elementary partition construction has at most K0 executions per block across all machines.Source: A The dense partition specialization · p. 28
  • The construction groups padded elementary blocks at two scales for each level, producing block partitions Bℓ and superblock partitions Sℓ, with Sℓ=Bℓ+1 for ℓ<q.Each superblock at one level is therefore a block at the next.Source: A The dense partition specialization · pp. 28–29
  • Each reference execution violates eligibility at no more than one level, so some level has at most |O′′|/q=η|O′′| ineligible executions.The argument distinguishes finer levels, where the execution’s superblock is spanned, from coarser levels, where its block contains a window endpoint.Source: A The dense partition specialization · p. 29
  • The selected level yields an aligned, eligible schedule with at most Kℓ∗ executions per block and at least (1−2η)OPT jobs.Among q levels, one has at most η|O′′| ineligible reference executions; deleting them leaves the schedule O′.Source: A The dense partition specialization · p. 29
  • For exact targets, at most H tests establish the optimum when the first infeasible target is reached, or certify OPT≥H if all tests succeed.These tests use all input jobs over [0,T) without partition restrictions and have total bounds nO(H) poly(N) and (2m)O(H) poly(n,T,N).Source: A The dense partition specialization · p. 29

B Complementary global-job rounding

The complementary rounding procedure assigns global jobs to block-machine pairs, discards long assignments, and tests the loads of short assignments before scheduling survivors. Its tests yield feasible block schedules, which can be combined feasibly.

B Complementary global-job rounding

  • Each global job is assigned to at most one block-machine pair with probability (1−2η)yj,B,i, while local jobs are excluded.The expected number of initial assignments is (1−2η)G.Source: B Complementary global-job rounding · pp. 30–31
  • The expected number of discarded long assignments is at most m∆|B|.Long means pj>η⁴|Ij,B|, where Ij,B is the job’s window intersected with its assigned block.Source: B Complementary global-job rounding · p. 30
  • Short assigned jobs face at most two load tests, and a job assigned with positive probability survives them conditionally with probability at least 1−2η.The survival bound follows by applying a Chernoff bound and a union bound over the tests.Source: B Complementary global-job rounding · pp. 30–31
  • The surviving jobs can be placed within each block using deadline-ordered and release-ordered groups around jobs that span the block.The passed load tests ensure enough space, and combining the block schedules is feasible because each job is assigned to at most one pair.Source: B Complementary global-job rounding · p. 31
  • The rounding procedure uses deterministic steps polynomial in the input and represented configuration supports, with at most one random assignment per global job.The implementation uses a bounded number of random bits.Source: B Complementary global-job rounding · p. 31

C Roadmap of the paper

Figure 8 outlines how the paper coordinates global jobs across blocks: it matches crossing pairs of good jobs, then coordinates the unmatched noncrossing family. Local jobs lie in one block; global jobs do not.

C Roadmap of the paper

  • Good global jobs have probability at least 1/4 at each boundary, and a maximal matching pairs jobs whose boundary endpoints alternate.The figure distinguishes local jobs, whose windows lie in one block, from global jobs.Source: Figure 8 · p. 32
  • The unmatched good jobs form a noncrossing family, and those recorded at both boundaries are coordinated.Full consistency records all jobs; interior assignments and exchanges are proof devices.Source: Figure 8 · p. 32
  • Solid arrows carry bounds, while dashed arrows supply inputs.Source: Figure 8 · p. 32
Loading 2610.34656v1…