CS Paper Radar

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

Weitian Tong, Yao Xu

cs.DS ·submitted 2026-08-16 02:56 UTC · v1

Abstract

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.

Comment
26 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-10-26 ·Weitian Tong, Yao Xu
similarity 0.66
Abstract · 34 pages, 8 figures

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.

0.15

A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization

cs.DS cs.DM ·2026-11-18 ·Mikhail Cherniavskii, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev, Fedor Ozhegov +1 more
similarity 0.62
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 $\varepsilon>0$, we give a randomized $(12/11+\varepsilon)$-approximation. This improves the recent $(4/3+\varepsilon)$-approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the $(17/13+\varepsilon)$-approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time $n^{O_\varepsilon(1)}\operatorname{poly}(N)$, where $N$ is the input length.

0.28

An EPTAS for Vector Scheduling with Time Intervals

cs.DS cs.CC ·2026-09-27 ·Junho Hwang
theory similarity 0.60
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

Approximation algorithms for identical parallel machine scheduling with assignment costs

cs.DS ·2026-10-24 ·Wei Li
similarity 0.59
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.59
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

Faster Exponential Algorithms for Multi-Machine Scheduling Problems

cs.DS ·2026-08-12 ·Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, Karol Węgrzycki
published similarity 0.59
Abstract

Minimizing the weighted completion times ($P \mid \mid Σw_j C_j$) and weighted number of tardy jobs ($P \mid \mid Σw_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid Σw_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid Σw_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

0.50

Speedup-Aware Rounding for Scheduling Malleable Tasks with Precedence Constraints

cs.DS ·2026-11-11 ·Chi-Yeh Chen
similarity 0.58
Abstract · 31 pages; ancillary files contain the numerical verification programs

We study the scheduling of malleable tasks with precedence constraints on $m$ identical processors to minimize the makespan, assuming that the processing time of a task does not increase and its work does not decrease with the number of processors, and that the work is a convex function of the processing time. The standard two-phase method solves a linear program, rounds the fractional processing times to allotments, caps the allotments at a threshold $μ$, and runs list scheduling. We propose \emph{speedup-aware rounding}, which rounds a task to its slower allotment exactly when this allotment is at most a factor $a$ slower than the fractional processing time. We determine the worst-case increase of the work under this rule exactly and show that no per-task rounding rule with time factor $a$ does better. With $μ=\lceilβ(a)m\rceil$ the algorithm achieves the approximation ratio $13(30+\sqrt{493})/225\approx3.0162$ for every $m$, which improves the previous bound $2+\sqrt2\approx3.4142$; a single task with linear speedup shows that its ratio is at least $\approx2.9558$. For concave speedup functions, which include the roofline, communication, Amdahl and power-law models, the ratio becomes $\approx2.9739$, which improves the ratio $\approx3.2919$ of Jansen and Zhang. We also revisit the strictly decreasing case of our earlier work (Chen and Chu, 2013): the reported ratio $2.9549$ relies on an elimination step that is not valid. In this case the algorithm coincides with that of Jansen and Zhang up to its parameters, and with parameters chosen by the corrected analysis it guarantees their ratio $\approx3.2919$. Finally, without convexity no per-task rounding improves the known time--work trade-off, and the analysis cannot go below $(3+\sqrt5)/2$.

0.47

Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times

cs.CC cs.DMmath.CO ·2026-09-23 ·Zhi-Long Chen, Nicholas G. Hall
theory similarity 0.57
Abstract · 38 pages, 2 figures, 5 tables

We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize total weighted tardiness. Although closely related equal-processing-time problems admit polynomial-time algorithms, the complexity of this problem has remained open in the literature since 2010. We prove that its decision version is strongly NP-complete, even when every job can meet its due date if processed immediately upon release. The reduction is from unweighted MAX-CUT and uses a quadratic number of jobs with polynomially bounded numerical data. Its main ingredient is a constructive normalization theorem that converts every sufficiently inexpensive feasible schedule into a binary choice for each graph vertex; after normalization, total weighted tardiness equals a constant minus a scaled cut value. We also give a deterministic polynomial-time phase-grid assignment algorithm for the shifted objective $Φ=F+p\sum_jw_j$, where $F$ is total weighted tardiness. The algorithm enumerates at most $N$ release-date residues modulo $p$, solves one minimum-cost assignment problem for each residue, and returns the best phase-grid schedule. It runs in $O(N^5)$ arithmetic operations and achieves the tight ratio $3/2-1/(2N)$ for this algorithm. Because the added term $p\sum_jw_j$ is independent of how the jobs are scheduled, the shifted and original objectives have exactly the same optimal schedules. However, the approximation guarantee applies to the shifted objective; for the original objective, the analysis provides an additive bound. Thus, the paper both resolves the long-standing complexity question and provides a complementary worst-case guarantee for the phase-grid assignment algorithm.

0.21