CS Paper Radar

Speedup-Aware Rounding for Scheduling Malleable Tasks with Precedence Constraints

Chi-Yeh Chen

cs.DS ·submitted 2026-11-11 06:40 UTC · v1

Abstract

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

Comment
31 pages; ancillary files contain the numerical verification programs

Closest papers

Nearest neighbours by meaning across the whole index.

Below Three: A 2.8027-Approximation for Moldable Precedence Scheduling

cs.DS ·2026-11-19 ·Klaus Jansen, Felix Ohnesorge
similarity 0.71
Abstract

We study makespan minimisation for nonpreemptive moldable jobs with arbitrary precedence constraints on identical processors. Each job runs on a chosen number of processors that remains fixed throughout its execution. Allocating more processors to a job can shorten its execution, but may increase total work and delay other jobs. We assume nonincreasing processing times, nondecreasing work, and a convex duration--work relation after dominated allocations are removed. This model includes jobs with concave speedup, for which Jansen and Zhang obtained a $3.291919\ldots$-approximation. Independently and concurrently with our work, Chen obtained a $3.016208\ldots$-approximation for the full convex model and a $2.973912\ldots$-approximation for concave speedup. We give a deterministic polynomial-time $2.8027$-approximation for the full convex model and every number of processors. Our result breaks the factor-three barrier for this model and also improves the approximation guarantee for concave speedup.

0.34

Tight bounds for fractional and randomized truthful scheduling

cs.GT ·2026-11-04 ·Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
theory similarity 0.63
Abstract

We resolve one of the longest-standing open problems in algorithmic mechanism design by showing that randomization cannot yield a sublinear approximation for truthful scheduling on unrelated machines, even when truthfulness is required only in expectation. Our main technical result concerns fractional scheduling, where tasks may be split among machines. We prove that every deterministic truthful fractional mechanism on $n$ unrelated machines has worst-case approximation ratio at least $(n+1)/2$, even against the optimal integral makespan. This matches the known upper bound exactly and settles the optimal approximation ratio of truthful fractional scheduling. Since the expected allocations and payments of a truthful-in-expectation mechanism define a truthful fractional mechanism, the same lower bound applies to all truthful-in-expectation mechanisms and, in particular, to all universally truthful mechanisms. On the positive side, we give a universally truthful mechanism with approximation ratio $n/2+o(n)$. Together, these results establish the optimal leading constant $1/2$ for randomized truthful scheduling. Thus, randomization improves on the optimal deterministic approximation ratio by an asymptotic factor of two, and no more.

0.18

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

cs.DS ·2026-10-26 ·Weitian Tong, Yao Xu
similarity 0.61
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

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

Product-Aware Deterministic Rounding for Quantized Matrix Multiplication

cs.LG cs.DScs.IT ·2026-09-11 ·Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal
similarity 0.59
Abstract · 30 pages, 7 figures

Scalar rounding decisions interact through matrix multiplication. We study deterministic product-aware rounding after scales, clipping bounds, and grids are fixed, with each active scalar choosing between adjacent levels. For dynamic activation rounding, null-space reduction preserves the relaxed product while leaving at most $r$ fractional decisions, where $r$ is the rank of the active gap-weighted weight block. Conditional-expectation completion gives a deterministic polynomial-time algorithm with squared product error at most $ \mathrm{OPT}_{\mathrm{dyn}}+rν_{\max}^2/4$, where $\mathrm{OPT}_{\mathrm{dyn}}$ is the best admissible error and $ν_{\max}$ is the largest row norm of that block. For reusable static weights, the exact expected product-loss metric is the uncentered input second moment with fixed output bias; free bias recalibration yields the centered covariance. Exact optimization is NP-hard even at rank one. In balanced blocks with $K=1024$ and $r=16$, conditional- expectation completion attains a dither-normalized median error of $0.010$, compared with $0.899$ for round-to-nearest. Clipping-aware initialization reduces median normalized error by a factor of $43.4$ at ten-percent clipping. Held-out Digits experiments show that retaining the input mean or correcting the output bias improves median product error over round-to-nearest in all four tested bit-width and calibration-size settings.

0.30

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

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

The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing

cs.DS math.OC ·2026-09-03 ·Adam Y. Shavit
code/data similarity 0.59
Abstract · 43 pages, 9 figures. v3: the beta < 1/2 seven-machine witness is certified in exact rational arithmetic; the strict-rule endpoint at beta = …

Wang and Sitters' 11/6-approximation for graph balancing (each job allowed on at most two machines) is not one algorithm but a set of permitted executions. Step 1 may return any feasible solution of the fractional relaxation. Step 3 may match remaining jobs to the rounding's slots in many ways. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, none reaching it, so 11/6 is the least constant bounding every permitted run. We then determine the worst-case guarantee, against the optimum itself, as a function of the big-job threshold beta, the fractional share at or above which Step 2 assigns a job. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We extend the same eligibility rule to 0 < beta <= 1/2, outside the range they state. There a big job's two shares can both reach the threshold, so Step 2 acquires a third choice. We determine it too: exactly 3/2 + (1-beta)floor(1/beta), hence unbounded as beta falls. The worst-case ratio is therefore known at every threshold in (0,1), and attained at none. Consequently 2/3 is the unique optimal threshold, and the guarantee jumps at one half and again at every threshold 1/k below it, rather than degrading smoothly. A companion note examines changes that leave the constant unchanged.

0.44