ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines

Lars Rohwedder

REVIEW 2 major objections 4 minor 1 cited by

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A fixed-parameter algorithm with exponent linear in the number of distinct processing times solves makespan minimization on uniform machines.

desk verdict Genuinely important p_max^{O(d)} algorithm for uniform-machine makespan with a correct core combinatorial proof, but the natural-encoding running-time claim depends on a sketched high-multiplicity implementation that needs a formal write-up. read the letter →

arxiv 2501.04859 v1 pith:QJAQTZNI submitted 2025-01-08 cs.DS

Lars Rohwedder This is my paper · ORCID

classification cs.DS MSC 68Q2568Q2790B3590C10

keywords makespanminimizationuniformmachinesfixed-parametertractabilityintegerprogrammingSteinitzlemmamultiwaypartitioninghigh-multiplicityencodingETHlowerbound

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that makespan minimization on uniform machines—scheduling jobs with given processing times onto machines with different speeds so the latest-finishing machine finishes as early as possible—is fixed-parameter tractable with the best possible parameter dependence. The parameter is the number of distinct processing times, and the claimed running time is $p_{\max}^{O(d)} n^{O(1)}$. Prior algorithms had a quadratic term in the exponent; this result reduces it to linear, matching a barrier imposed by the exponential-time hypothesis. The practical point is that instances with few distinct job sizes, even with many machines and large processing times, become solvable exactly rather than only approximately.

What carries the argument

The load-bearing object is mod-IP($a$), a relaxation of Multiway Partitioning in which machines with small load targets must match their target exactly, while machines with large targets only need to match it modulo a pivot processing time $a$; a third constraint forces enough pivot-sized jobs onto the big machines. Feasibility of mod-IP($a$) is shown to imply feasibility of the original partition, regardless of $a$. The argument is carried by a new algorithm for Multi-Choice Integer Programming that builds a layered graph whose vertices are right-hand sides within a bounded distance of a balanced interpolation path and solves a longest-path problem; the Steinitz Lemma guarantees that an optimal solution corresponds to such a path. The configuration-based integer program for mod-IP($a$) has only $O(d)$ rows and coefficient bound $p_{\max}^4$, so plugging it into the Multi-Choice solver yields the $p_{\max}^{O(d)} n^{O(1)}$ bound.

What would settle it

Construct instances with binary-encoded machine speeds so that the total dummy work $T_{\text{total}} - p_{\text{total}}$ is exponential in the encoding length (for example, one very fast machine with speed $2^L$), run the high-multiplicity implementation, and measure whether the greedy phases take time polynomial in the compact encoding; super-polynomial growth would refute the high-multiplicity claim.

Watch

Extended reading notes

Core claim

The central claim is that the decision version of uniform-machine makespan can be reduced to an intermediate problem, Multiway Partitioning, and that feasibility of a relaxed modulo integer program—where machines with large load targets only need their load correct modulo a chosen pivot processing time—already implies a genuine partition. The paper proves this by a three-phase greedy reconstruction: strip bundles of equal-sized jobs from big machines, add them back one bundle at a time using a slack argument rooted in the Steinitz Lemma, then add back the pivot-sized jobs individually. Because the relaxed program has fewer exact constraints, it can be solved by a new Multi-Choice Integer Programming algorithm in time $p_{\max}^{O(d)} n^{O(1)}$, and a binary-search reduction transfers the bound to the original makespan problem. This answers the open question of whether the previous quadratic-in-$d$ exponent could be improved to a linear one.

Load-bearing premise

The running-time bound for naturally encoded inputs depends on the Section 5 claim that the large number of dummy jobs introduced in the binary-search reduction can be handled in a high-multiplicity way without materializing them one by one; if that sketch fails, the $p_{\max}^{O(d)} n^{O(1)}$ result for the original encoding does not follow.

Editorial extensions

If this is right

The open question about whether the exponent in the number of distinct processing times can be made linear is settled: under ETH, no algorithm with exponent $o(d)$ is possible, so the dependence is essentially optimal.
For instances encoded in high-multiplicity form, where multiplicities rather than individual jobs are listed, the same algorithm can be implemented in time $p_{\max}^{O(d)} \langle\text{enc}\rangle^{O(1)}$, avoiding an exponential gap in encoding length.
The identical-machine special case, previously known with a $p_{\max}^{O(d)}$ bound, is subsumed, and the uniform-machine case is closed at the same parameter dependence.
The Multi-Choice Integer Programming solver is stated generically and can be reused on other problems that fit its block-partition structure with small coefficients.
Binary search over the $O(\log(n m p_{\max}))$ candidate makespans preserves the fixed-parameter bound, so finding the optimum rather than merely deciding a deadline costs only polynomial overhead.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The modulo-relaxation idea might transfer to other hard partition or scheduling problems: identify a pivot item type, require exact targets only for small machines and congruence plus a quota for large ones, and try all possible pivots instead of knowing the right one in advance.
A practical speedup is plausible when $d$ is small but $n$ is huge, because the algorithm's dependence on $n$ is polynomial while the exponential part depends only on $p_{\max}$ and $d$; exact solutions could become feasible in regimes where ILP solvers are currently used only approximately.
The high-multiplicity implementation suggests a concrete stress test: generate instances with binary-encoded speeds that make the total dummy-work $T_{\text{total}} - p_{\text{total}}$ exponential in the encoding length, and verify that the greedy phases still terminate in $O(md)$ steps per phase, confirming the compact-encoding claim in practice.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Here's my read on Rohwedder's paper.

The headline is real: it gives an algorithm for makespan on uniform machines running in p_max^{O(d)} n^{O(1)}, improving the long-standing p_max^{O(d^2)} from n-fold ILP and answering the Koutecký–Zink open question. The core idea—relaxing big-machine loads to congruences modulo a pivot processing time, then repairing with a greedy—is clever and, as far as I can trace, correct. The Steinitz-based multi-choice IP solver is a solid contribution in its own right, and the configuration ILP reduction is standard.

What's genuinely good: the deficit arguments in Lemmas 3 and 4 are clean, and the search over the pivot a is handled honestly by trying all d values. The paper doesn't hide constants or hand-wave the main combinatorial argument. The improvement from quadratic to linear exponent is exactly what the community asked for.

The soft spot is exactly where the stress-test points. The reduction to Multiway Partitioning adds T_total − p_total dummy jobs of size 1. With binary machine speeds, that count is exponential in the input length. The Multiway Partitioning algorithm itself is oblivious to the number of jobs, running in p_max^{O(d)} m^{O(1)} via the configuration ILP, but the greedy repair phase as written in Section 2 iterates over jobs. Section 5 promises a batched high-multiplicity implementation in O(md) time, but it's a sketch, not a theorem. It doesn't prove that the batched Phase II/III preserves the slack invariants, nor does it specify how the ILP solution is represented as multiplicities. So the natural-encoding claim in Theorem 1 is not fully established as written. This is patchable—the batching is almost certainly correct—but it needs a formal treatment.

Minor quibble: the "ETH-tight" label is a bit generous. The cited lower bound is for the parameter U (the makespan bound), and the jump to "no p_max^{o(d)}" isn't a formal consequence. The paper's result is very likely optimal in the sense that matters, but the tightness claim is more heuristic than proven.

Bottom line: this is a significant paper and should be refereed. The core algorithm is credible and important; the author should be asked to fully prove the high-multiplicity implementation or restate the main theorem for that encoding. I'd bring it to a reading group and would cite it once the encoding gap is closed.

Referee Report

2 major / 4 minor

Summary. The paper gives an FPT algorithm for Makespan Minimization on Uniform Machines with running time p_max^{O(d)} n^{O(1)}, where p_max is the largest processing time and d is the number of distinct processing times. The proof proceeds through an intermediate Multiway Partitioning problem, a relaxed integer program mod-IP(a) that only enforces exact loads on small machines and congruence modulo a on large machines, and a generic Multi-Choice Integer Programming solver based on the Steinitz lemma. A greedy repair argument converts any feasible solution of mod-IP(a) into an exact partition. The paper also sketches a high-multiplicity implementation and claims an ETH-tight dependence on d, improving the previous p_max^{O(d^2)} bound and answering an open question of Koutecký and Zink.

Significance. If the claimed running time is fully established, this is a significant result: it settles the open question on the exponent in d, matches the ETH lower bound up to the base of the exponent, and introduces a modular-arithmetic technique plus a generic Multi-Choice Integer Programming theorem that may be of independent interest. The structure of the proof is elegant: the pivot choice is handled by trying all d processing times, the Steinitz-based path argument is a natural extension of Eisenbrand--Weismantel, and the configuration ILP reduction is standard. I also credit the paper for being explicit about the dependency of the lower bound on ETH and for identifying the high-multiplicity encoding as the delicate point. However, as detailed below, the central running-time claim is not fully proven as written, because the natural-encoding statement relies on a high-multiplicity implementation that is only sketched.

major comments (2)

[§4 (end) and §5] The running-time claim in Theorem 1 is not established as written. The reduction at the end of Section 4 adds T1+...+Tm - p1-...-pn dummy jobs of size 1; when machine speeds are encoded in binary, this quantity is not polynomially bounded in the input length. The Multiway Partitioning algorithm of Section 2 is analyzed with respect to the number n of jobs (Theorem 5), so applying it literally to the augmented instance would make the n in p_max^{O(d)} n^{O(1)} the number of dummy jobs rather than the original n. The only place where this is addressed is the short sketch in Section 5, which asserts without proof that the configuration ILP can be solved in p_max^{O(d)} m^{O(1)} and that the greedy phase can be batched in O(md) steps. Section 5 does not state a formal theorem, does not prove that the batched Phase II/III procedure preserves the invariants of Lemmas 3 and 4, and does not specify how the configuration-IP solution is converted into the implicit O(md)-size assignment used by the greedy. Since the abstract and Theorem 1 advertise a running time polynomial in the original n, the central result requires either a full formalization of Section 5 or a different reduction that avoids an exponential number of dummy jobs.
[§3.2, Lemma 6] There is an off-by-one error in the proof of Lemma 6. After iteration k, for a choice set S the number s_S of performed increments satisfies s_S ∈ {ceil(d_k t_S)-1, ceil(d_k t_S)}, not s_S ∈ {ceil(d_k t_S), floor(d_k t_S)+1} as claimed. The lower value occurs when d_k is not a breakpoint of S or when d_k is a breakpoint at which S has not yet acted because of a tie. Consequently the padding vector in the displayed inequality should be A_{σ_S(ceil(d_k t_S))}, not A_{σ_S(floor(d_k t_S)+1)}; the written index is wrong in the integer-breakpoint case. The argument can be repaired with the correct inclusion and the bound ‖(ceil(d_k t_S)/t_S - d_k) Ax(S)‖∞ ≤ Δ, which yields the same O(dΔ|P|) bound, but as written the proof of the path-existence statement has a gap. Since Lemma 6 is load-bearing for Theorem 2, the proof should be rewritten.

minor comments (4)

[§3.1] The layered graph is defined with vertex sets V_1,...,V_{t+1} and centers d_k b, but d_k is only defined for k=1,...,t; the definition should set d_{t+1}=1 (and possibly d_0=0 for V_1) so that V_{t+1} contains the target vertex b.
[Theorem 2 and Corollary 8] The running-time expression (mΔ|P|)^{O(m)} uses m, although the matrix is d×n; either define m as the number of rows or replace m by d consistently throughout the statements.
[§5] The high-multiplicity paragraph says the input contains 'machine speeds s_1,...,s_d'; this should be s_1,...,s_m, since the number of machines need not equal d.
[§1, abstract] The abstract and the introduction describe the high-multiplicity implementation as a secondary contribution, but Section 5 is only a sketch; adding a formal theorem statement for the high-multiplicity running time would make the paper's claims easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the pivot is enumerated over all d candidates, the mod-IP repair is proven independently, and no prediction is fitted from the input.

full rationale

The paper's derivation chain is self-contained. The pivot a in Section 2 is the only place where the unknown optimal solution appears, but Lemma 9 merely proves existence of some a among {p1,...,pn}, and the paper explicitly avoids circularity by trying each of the d possible choices: 'We can avoid this issue by later attempting to solve the model for each of the d possible choices of a.' Theorem 5 then gives a self-contained proof that any feasible mod-IP(a) solution can be greedily repaired into an exact Multiway Partitioning; this direction does not presuppose the partition it is trying to find. The ILP engine in Section 3 relies on the Steinitz Lemma from [18]/[6], an external standard result, and the path construction is proved in Lemma 6. The self-citations are not load-bearing: [11] is explicitly not used as a black box, and [17] is cited only for an overview of integer-programming gaps. The ETH-based lower bound is imported from [3] as an external complexity hypothesis. The one material weakness is non-circular: Section 5 is only a sketch asserting that the greedy repair can be batched in O(md) without formally proving the invariants of Lemmas 3 and 4 in the high-multiplicity setting, and the dummy-job reduction in Section 4 can add an exponentially large number of jobs relative to the encoding length. This is a proof-completeness or correctness risk for the natural-encoding running-time claim, not a case of the conclusion being assumed as an input or a fitted parameter being renamed as a prediction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No parameter is fitted to data. The algorithm's correctness relies on the standard Steinitz lemma and elementary counting; ETH is imported only for the lower-bound optimality claim. The paper posits no new physical or unexplained mathematical entities beyond the mod-IP formulation and the multi-choice ILP abstraction, which are part of the algorithm.

assumptions (3)

standard math Steinitz Lemma (Proposition 7)
Used in Lemma 6 to bound partial sums of columns by the dimension d; taken as an external theorem from [18].
domain assumption Exponential Time Hypothesis (ETH)
Used to argue the p_max^{O(d)} exponent is essentially best possible; not used for the correctness of the algorithm.
standard math Pigeonhole principle over d processing times
Used in Lemma 9 to select a pivot a with enough jobs of size a on big machines; relies on d <= p_max.

how reviews work

0 comments

Cite this review

Pith. "Pith review of ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines." pith.science (2026). https://pith.science/paper/QJAQTZNI

@misc{pith2026250104859,
  author       = {Pith},
  title        = {Pith review of: ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QJAQTZNI}},
  note         = {Machine review of arXiv:2501.04859}
}

abstract

Given $n$ jobs with processing times $p_1,\dotsc,p_n\in\mathbb N$ and $m\le n$ machines with speeds $s_1,\dotsc,s_m\in\mathbb N$ our goal is to allocate the jobs to machines minimizing the makespan. We present an algorithm that solves the problem in time $p_{\max}^{O(d)} n^{O(1)}$, where $p_{\max}$ is the maximum processing time and $d\le p_{\max}$ is the number of distinct processing times. This is essentially the best possible due to a lower bound based on the exponential time hypothesis (ETH). Our result improves over prior works that had a quadratic term in $d$ in the exponent and answers an open question by Kouteck\'y and Zink. The algorithm is based on integer programming techniques combined with novel ideas based on modular arithmetic. They can also be implemented efficiently for the more compact high-multiplicity instance encoding.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma
cs.DS 2025-07 conditional novelty 3.0 of 10

A Steinitz-lemma-based algorithm solves combinatorial n-fold ILPs with unbounded non-negative variables, giving 2^{O(k^2)}-time algorithms for Lobbying and Binary Closest String.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

[1]

Knapsack with small items in near-quadr atic time

Karl Bringmann. Knapsack with small items in near-quadr atic time. In Pro- ceedings of STOC , pages 259–270, 2024

work page 2024
[2]

Structural Results for High-Multiplicity Scheduling on Uniform Machines

Hauke Brinkop, David Fischer, and Klaus Jansen. Structu ral results for high- multiplicity scheduling on uniform machines. CoRR, abs/2203.01741, 2024

work page Pith review arXiv 2024
[3]

On the optima lity of approx- imation schemes for the classical scheduling problem

Lin Chen, Klaus Jansen, and Guochuan Zhang. On the optima lity of approx- imation schemes for the classical scheduling problem. In Proceedings SODA, pages 657–668, 2014

work page 2014
[4]

Fas ter algorithms for bounded knapsack and bounded subset sum via ﬁne-grained pro ximity results

Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. Fas ter algorithms for bounded knapsack and bounded subset sum via ﬁne-grained pro ximity results. In Proceedings SODA, pages 4828–4848, 2024

work page 2024
[5]

Block-structured integer and linear program- ming in strongly polynomial and near linear time

Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hun kenschröder, Lars Ro- hwedder, and Robert Weismantel. Block-structured integer and linear program- ming in strongly polynomial and near linear time. In Proceedings of SODA , pages 1666–1681, 2021

work page 2021
[6]

Proximity results and faster al- gorithms for integer programming using the steinitz lemma

Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster al- gorithms for integer programming using the steinitz lemma. ACM Transactions on Algorithms (TALG) , 16(1):1–14, 2019

work page 2019
[7]

Polynomiality for b in packing with a constant number of item types

Michel X Goemans and Thomas Rothvoß. Polynomiality for b in packing with a constant number of item types. Journal of the ACM (JACM) , 67(6):1–21, 2020. 11

work page 2020
[8]

An eptas for scheduling jobs on uniform pro cessors: using an milp relaxation with a constant number of integral variable s

Klaus Jansen. An eptas for scheduling jobs on uniform pro cessors: using an milp relaxation with a constant number of integral variable s. SIAM Journal on Discrete Mathematics , 24(2):457–485, 2010

work page 2010

Show all 18 references

[9]

Improving the parameter dependency for high-multiplicity scheduling on uniform machines

Klaus Jansen, Kai Kahler, Lis Pirotton, and Malte Tutas. Improving the parameter dependency for high-multiplicity scheduling on uniform machines. CoRR, abs/2409.04212, 2024

2024
[10]

Clo sing the gap for makespan scheduling via sparsiﬁcation techniques

Klaus Jansen, Kim-Manuel Klein, and José Verschae. Clo sing the gap for makespan scheduling via sparsiﬁcation techniques. Mathematics of Operations Research, 45(4):1371–1392, 2020

2020
[11]

On integer programmin g, discrepancy, and convolution

Klaus Jansen and Lars Rohwedder. On integer programmin g, discrepancy, and convolution. Mathematics of Operations Research , 48(3):1481–1495, 2023

2023
[12]

0-1 knapsack in nearly quadratic time

Ce Jin. 0-1 knapsack in nearly quadratic time. In Proceedings STOC, pages 271–282, 2024

2024
[13]

Scheduling meets n-fol d integer program- ming

Dusan Knop and Martin Koutecký. Scheduling meets n-fol d integer program- ming. Journal on Scheduling , 21(5):493–503, 2018

2018
[14]

Complexity of sched uling few types of jobs on related and unrelated machines

Martin Koutecký and Johannes Zink. Complexity of sched uling few types of jobs on related and unrelated machines. In Proceedings of ISAAC, volume 181, pages 18:1–18:17, 2020

2020
[15]

Scheduling and ﬁxed- parameter tractabil- ity

Matthias Mnich and Andreas Wiese. Scheduling and ﬁxed- parameter tractabil- ity. Mathematical Programming, 154(1-2):533–562, 2015

2015
[16]

Knaps ack and subset sum with small items

Adam Polak, Lars Rohwedder, and Karol Węgrzycki. Knaps ack and subset sum with small items. In Proceeding of ICALP, pages 1–19, 2021

2021
[17]

Fine-grained equi valence for problems related to integer linear programming

Lars Rohwedder and Karol Wegrzycki. Fine-grained equi valence for problems related to integer linear programming. In Proceedings of ITCS, 2025

2025
[18]

Approximate solution of some problems of scheduling theory

S Sevast’janov. Approximate solution of some problems of scheduling theory. Metody Diskret. Analiz , 32:66–75, 1978. 12

1978

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Knapsack with small items in near-quadr atic time

Karl Bringmann. Knapsack with small items in near-quadr atic time. In Pro- ceedings of STOC , pages 259–270, 2024

work page 2024

[2] [2]

Structural Results for High-Multiplicity Scheduling on Uniform Machines

Hauke Brinkop, David Fischer, and Klaus Jansen. Structu ral results for high- multiplicity scheduling on uniform machines. CoRR, abs/2203.01741, 2024

work page Pith review arXiv 2024

[3] [3]

On the optima lity of approx- imation schemes for the classical scheduling problem

Lin Chen, Klaus Jansen, and Guochuan Zhang. On the optima lity of approx- imation schemes for the classical scheduling problem. In Proceedings SODA, pages 657–668, 2014

work page 2014

[4] [4]

Fas ter algorithms for bounded knapsack and bounded subset sum via ﬁne-grained pro ximity results

Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. Fas ter algorithms for bounded knapsack and bounded subset sum via ﬁne-grained pro ximity results. In Proceedings SODA, pages 4828–4848, 2024

work page 2024

[5] [5]

Block-structured integer and linear program- ming in strongly polynomial and near linear time

Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hun kenschröder, Lars Ro- hwedder, and Robert Weismantel. Block-structured integer and linear program- ming in strongly polynomial and near linear time. In Proceedings of SODA , pages 1666–1681, 2021

work page 2021

[6] [6]

Proximity results and faster al- gorithms for integer programming using the steinitz lemma

Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster al- gorithms for integer programming using the steinitz lemma. ACM Transactions on Algorithms (TALG) , 16(1):1–14, 2019

work page 2019

[7] [7]

Polynomiality for b in packing with a constant number of item types

Michel X Goemans and Thomas Rothvoß. Polynomiality for b in packing with a constant number of item types. Journal of the ACM (JACM) , 67(6):1–21, 2020. 11

work page 2020

[8] [8]

An eptas for scheduling jobs on uniform pro cessors: using an milp relaxation with a constant number of integral variable s

Klaus Jansen. An eptas for scheduling jobs on uniform pro cessors: using an milp relaxation with a constant number of integral variable s. SIAM Journal on Discrete Mathematics , 24(2):457–485, 2010

work page 2010