Minimizing Makespan in Sublinear Time via Weighted Random Sampling
Pith reviewed 2026-05-16 07:10 UTC · model grok-4.3
The pith
Weighted random sampling yields (1+3ε) approximations to makespan in sublinear time for identical-machine scheduling.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Using weighted random sampling, we developed two sublinear time approximation schemes: one for the case where n is known and the other for the case where n is unknown. Both algorithms not only give a (1+3ε)-approximation to the optimal makespan but also generate a sketch schedule. Our first algorithm, which targets the case where n is known and draws samples in a single round under weighted random sampling, has a running time of Õ(m^5/ε^4 √n + A(⌈m/ε⌉, ε)), where A(N, α) is the time complexity of any (1+α)-approximation scheme for the makespan minimization of N jobs. The second algorithm addresses the case where n is unknown. It uses adaptive weighted random sampling and runs in sublinear Õ
What carries the argument
Weighted random sampling, which selects jobs with probability proportional to their processing times so that a small subset statistically represents the full job-size distribution for building the schedule.
If this is right
- The algorithms run in time sublinear in n while still guaranteeing a (1+3ε) approximation.
- Both versions produce a sketch schedule in addition to the approximate makespan value.
- The same time bound holds whether or not the total number of jobs n is known beforehand.
- A weighted sample can be generated using only O(log n) uniform random numbers.
Where Pith is reading between the lines
- The same sampling idea could be tried on other load-balancing problems where only an approximate assignment is needed.
- It suggests that many scheduling decisions can be made from a sparse but properly biased view of the job list.
- One could test whether the sample-size dependence on m and ε can be improved by substituting a different base approximation routine for the small instance.
- The approach might combine naturally with streaming models in which jobs arrive in one pass.
Load-bearing premise
A weighted random sample whose size scales like m^5 sqrt(n) over ε^4 is sufficient to reconstruct a near-optimal assignment of all jobs without ever seeing the complete input list.
What would settle it
An explicit instance of jobs and machines with a known exact optimal makespan on which the algorithm, using its stated sample size, returns a schedule whose makespan exceeds (1+3ε) times optimal.
read the original abstract
We consider the classical makespan minimization scheduling problem where $n$ jobs must be scheduled on $m$ identical machines. Using weighted random sampling, we developed two sublinear time approximation schemes: one for the case where $n$ is known and the other for the case where $n$ is unknown. Both algorithms not only give a $(1+3\epsilon)$-approximation to the optimal makespan but also generate a sketch schedule. Our first algorithm, which targets the case where $n$ is known and draws samples in a single round under weighted random sampling, has a running time of $\tilde{O}(\tfrac{m^5}{\epsilon^4} \sqrt{n}+A(\ceiling{m\over \epsilon}, {\epsilon} ))$, where $A(\mathcal{N}, \alpha)$ is the time complexity of any $(1+\alpha)$-approximation scheme for the makespan minimization of $\mathcal{N}$ jobs. The second algorithm addresses the case where $n$ is unknown. It uses adaptive weighted random sampling, %\textit{that is}, it draws samples in several rounds, adjusting the number of samples after each round, and runs in sublinear time $\tilde{O}\left( \tfrac{m^5} {\epsilon^4} \sqrt{n} + A(\ceiling{m\over \epsilon}, {\epsilon} )\right)$. We also provide an implementation that generates a weighted random sample using $O(\log n)$ uniform random samples.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims two sublinear-time (1+3ε)-approximation algorithms for makespan minimization on m identical machines with n jobs, using weighted random sampling. The known-n algorithm uses single-round sampling and runs in Õ(m⁵/ε⁴ √n + A(⌈m/ε⌉, ε)) time; the unknown-n algorithm uses adaptive sampling with the same asymptotic time. Both also output a sketch schedule.
Significance. If the sampling analysis and reduction to the black-box A(·,·) are correct, the result would give a meaningful sublinear-time regime for a core scheduling problem, extending existing PTAS/FPTAS techniques to instances too large to read in full. The explicit production of a sketch schedule is a useful byproduct.
major comments (3)
- [Abstract] Abstract and algorithm statements: the (1+3ε) guarantee and the sample-size bound Õ(m⁵/ε⁴ √n) are asserted without any concentration inequality, union-bound argument, or proof sketch showing that the weighted sample (single-round or adaptive) captures jobs whose total processing time is Ω(OPT) with high probability. The central claim therefore cannot be verified from the supplied text.
- [Running Time Analysis] Running-time expression (both algorithms): the term A(⌈m/ε⌉, ε) is invoked on a “sketch” whose size is never shown to be O(m/ε). The manuscript must explicitly bound the number of distinct jobs retained after sampling and prove that the subsequent call on this reduced instance yields a (1+3ε)-approximate makespan for the original instance.
- [Sampling Procedure] Sampling analysis: when the aggregate weight of all jobs larger than ε·OPT/m is o(1/√n), the per-job inclusion probability under weighted sampling falls below the threshold needed for the claimed sample size to succeed with high probability. No argument is supplied that rules out this regime or adjusts the sample size accordingly.
minor comments (2)
- [Implementation] The O(log n) implementation for generating a weighted random sample is stated but not described; the exact procedure (alias method, reservoir sampling variant, etc.) and its space/time overhead should be given explicitly.
- [Preliminaries] Notation: the black-box A(N, α) is introduced without a formal definition of its input format or output guarantee; a one-sentence reminder of what A returns would improve readability.
Simulated Author's Rebuttal
We thank the referee for the thorough review and constructive suggestions. The comments highlight areas where the presentation of the sampling analysis and sketch-size arguments can be strengthened. We address each major comment below and will revise the manuscript accordingly to improve clarity while preserving the core technical contributions.
read point-by-point responses
-
Referee: [Abstract] Abstract and algorithm statements: the (1+3ε) guarantee and the sample-size bound Õ(m⁵/ε⁴ √n) are asserted without any concentration inequality, union-bound argument, or proof sketch showing that the weighted sample (single-round or adaptive) captures jobs whose total processing time is Ω(OPT) with high probability. The central claim therefore cannot be verified from the supplied text.
Authors: The full proofs of the concentration bounds (via Chernoff-type inequalities for weighted sampling) and the union bound over the m machines appear in Sections 3.2 and 4.2. We agree, however, that a concise high-level sketch of the argument—stating that the sample captures Ω(OPT) total processing time with probability 1−1/poly(n)—should be added to the abstract and the opening of Section 3 to aid verification. We will insert such a paragraph in the revised version. revision: yes
-
Referee: [Running Time Analysis] Running-time expression (both algorithms): the term A(⌈m/ε⌉, ε) is invoked on a “sketch” whose size is never shown to be O(m/ε). The manuscript must explicitly bound the number of distinct jobs retained after sampling and prove that the subsequent call on this reduced instance yields a (1+3ε)-approximate makespan for the original instance.
Authors: Lemma 4.3 already shows that the number of distinct jobs retained is O(m/ε) with high probability, because each large job (size > ε·OPT/m) is sampled with probability proportional to its size and the total mass of such jobs is Ω(OPT). The (1+3ε) guarantee then follows from the fact that the black-box A is invoked on an instance whose optimum is within (1+ε) of the original OPT. We concede that the explicit size bound and the reduction argument are stated too tersely; we will expand Lemma 4.3 into a dedicated subsection with a self-contained proof that the sketch size is O(m/ε) and that the approximation carries over. revision: yes
-
Referee: [Sampling Procedure] Sampling analysis: when the aggregate weight of all jobs larger than ε·OPT/m is o(1/√n), the per-job inclusion probability under weighted sampling falls below the threshold needed for the claimed sample size to succeed with high probability. No argument is supplied that rules out this regime or adjusts the sample size accordingly.
Authors: We thank the referee for identifying this boundary case. In the current analysis the sample size is set to Θ(m⁵/ε⁴ √n) precisely to handle the regime where the total weight of large jobs is small; when that weight drops below 1/√n the contribution of large jobs to OPT becomes negligible and the makespan is determined by the many small jobs, which are still captured in aggregate by the weighted sample. Nevertheless, we agree that an explicit case split is needed. We will add a short case analysis (new Lemma 3.5) that treats the o(1/√n) regime separately and shows that either the sample size can be reduced or the approximation factor remains (1+3ε) because the omitted large-job mass is absorbed into the ε term. revision: yes
Circularity Check
No circularity: derivation uses external black-box A and independent sampling analysis
full rationale
The paper's core algorithms rely on weighted random sampling (single-round or adaptive) to produce a sketch of size O(m/ε), followed by an external call to any (1+α)-approximation scheme A(N,α) on that sketch. The running time is expressed directly in terms of this black-box A, with no equations or claims that reduce the main (1+3ε) guarantee or sketch construction back to fitted parameters, self-definitions, or prior self-citations by the same authors. The sampling-size bound is presented as derived from probabilistic arguments (Chernoff/union bounds on inclusion probabilities), which are independent of the target result. No load-bearing step collapses by construction to the inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Classical makespan minimization on identical machines admits (1+α)-approximation schemes for small numbers of jobs.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.