CS Paper Radar

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

Weitian Tong, Yao Xu

cs.DS ·submitted 2026-10-26 00:39 UTC · v1

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 $\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.

Comment
34 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A QPTAS for Stochastic Scheduling of Bernoulli Jobs

cs.DS cs.CCmath.OC ·2026-10-08 ·Junho Hwang
benchmark similarity 0.69
Abstract · 23 pages, 1 figure

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $Ω(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.

0.25

Approximation algorithms for identical parallel machine scheduling with assignment costs

cs.DS ·2026-10-24 ·Wei Li
similarity 0.68
Abstract

We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$. The processing times $p_j$ and the cost weights $w_j$ are independent, and the number of machines is part of the input. For every fixed $\varepsilon\in(0,1]$ and every deadline $T$ for which a schedule with makespan at most $T$ exists, we give a polynomial-time algorithm that computes a schedule with makespan at most $(1+\varepsilon)T$ whose total assignment cost does not exceed the minimum under the deadline $T$. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs $c_{ij}=l_ic_j$ with $c_j$ independent of $p_j$. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most $1+\varepsilon$ times the minimum and total assignment cost at most that of a lexicographically optimal schedule; this improves the makespan guarantees of earlier algorithms for additive and multiplicative costs. For costs $c_{ij}=s_i+a_iw_j$, where $s_i$ is charged for each job processed on $M_i$, the same guarantees are obtained in quasi-polynomial time.

0.24

Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date

cs.CC math.OCcs.DMmath.CO ·2026-09-12 ·Nicholas G. Hall, Hans Kellerer, Miao Song
similarity 0.68
Abstract · 268 pages, 12 figures, 29 tables

Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date $d=\sum_jp_j$, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time $(3+2\sqrt2+\varepsilon)$-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.

0.21

Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling

cs.DS ·2026-10-23 ·Sven Jäger, Alexander Lindermayr, Bart Zondervan
theory similarity 0.66
Abstract · Shortened abstract

The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm. On a single machine, PF coincides with weighted Round-Robin, which is $2$-competitive for weighted completion time with uniform release dates (optimal for nonclairvoyant algorithms) and $(2+\varepsilon)$-speed $O(1/\varepsilon)$-competitive for weighted flow time. Known guarantees beyond a single machine are weaker. This raises a central question: Are these heterogeneous environments intrinsically harder than a single machine under nonclairvoyance? We show that they are not: PF retains both single-machine guarantees on the novel class of support-submodular polytopes, which includes unrelated machines and polymatroids. On unrelated machines, this refutes a belief (JACM'18, SODA'25) that PF is not $O(1)$-speed $O(1)$-competitive for weighted flow time. Our main technical contribution is an equivalent characterization: a polytope is support submodular if and only if, for all job weights, the optimal weighted completion time is concave in the processing requirements. This structural insight underlies both guarantees. For general PSP, the picture changes: we give the first lower bound above $2$, showing that every randomized nonclairvoyant algorithm has a competitive ratio of at least $2+10^{-5}$ for weighted completion time, even with uniform release dates. On the positive side, we substantially improve the best known guarantee for weighted completion time from $27$ (SICOMP'26) to $4$ via a new dual-fitting analysis of PF. For weighted flow time, we show that PF achieves the first $O(1)$-speed $O(1)$-competitive nonclairvoyant guarantee for graph scheduling.

0.27

Sharp Bounds for Truthful-in-Expectation Scheduling

cs.GT ·2026-11-03 ·Yunpeng Li
theory similarity 0.66
Abstract

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

0.18

Cross-Shift Analysis for Unrelated-Machine Weighted Completion Time A (1.3168+epsilon)-Approximation

cs.DS ·2026-08-16 ·Weitian Tong, Yao Xu
similarity 0.66
Abstract · 26 pages, 2 figures

We study the problem of minimizing total weighted completion time on unrelated parallel machines with machine-independent job weights. The best previous approximation guarantee for this problem is arbitrarily close to 1.36, due to Li [SODA 2025], who developed a configuration-LP and iterative-rounding framework based on randomly shifted geometric size classes and a computer-assisted final analysis. We improve the approximation guarantee to arbitrarily close to 1.3168. The scheduling algorithm retains Li's configuration-LP and iterative-rounding framework, with a different fixed geometric class ratio. The improvement comes from a new analysis of the random geometric shift. For each machine and Smith prefix, we normalize the physical prefix before averaging over the shift, so that its normalized size distribution and configuration moments remain fixed across all shifts. A scale-dependent configuration bound and a cross-shift averaging argument then reduce the approximation analysis to a one-dimensional certificate. The final certificate is computer assisted and reproducible. Its rational data are verified exactly where possible, while the remaining continuous inequalities are certified using directed interval arithmetic. This yields the first improvement over Li's guarantee for the machine-independent-weight model.

0.10

Scheduling to Maximize Weighted Throughput with an Active-Time Budget

cs.DS ·2026-08-29 ·Susanne Albers, G. Wessel van der Heijden
publishedtheory similarity 0.66
Abstract · 16 pages, 5 figures, To appear at WAOA 2026

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

0.25

An EPTAS for Vector Scheduling with Time Intervals

cs.DS cs.CC ·2026-09-27 ·Junho Hwang
theory similarity 0.66
Abstract · 18 pages, 4 figures. v2: extended to several resources and unrelated machines, with a new title and simplified proofs

We study vector scheduling in which each job is active during a fixed time interval. A job uses several resources and stays on one machine for its entire interval; its resource requirements may depend on the machine. The objective is to minimize the largest resource load over all machines and times. For $r$ machines and $d$ resources, we give a deterministic $(1+\varepsilon)$-approximation in $f(r,d,1/\varepsilon)N^{O(1)}$ time, where $N$ is the binary input length. This gives an efficient polynomial-time approximation scheme for fixed $r$ and $d$, extending approximation schemes for scalar temporary tasks assignment. The algorithm merges jobs into blocks whose time intervals are fixed before any machine is chosen, and assigns the blocks by dynamic programming over a balanced recursive split of the time line. We also prove strong NP-hardness and an exponential lower bound in $1/\varepsilon$ under the Exponential Time Hypothesis, already for two identical machines and one resource.

0.13