{"id":"ed019ed7-2352-4da3-ac2d-8af2feda5db7","arxiv_id":"2501.04859","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Makespan minimization on uniform machines is solved in time p_max^{O(d)} n^{O(1)}, settling an open question by Koutecký and Zink with an ETH-tight exponent.","lead":"This paper gives a faster exact algorithm for assigning jobs to machines of different speeds to minimize the latest finishing time. The running time improves from p_max^{O(d^2)} to p_max^{O(d)}, matching a known lower bound up to the base of the exponent.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The natural-encoding running-time claim depends entirely on Section 5's high-multiplicity batching, which is only sketched and not formally proven.","rationale":"I independently traced the main argument. The modular relaxation in Section 2, the Steinitz-based Multi-Choice IP in Section 3, and the configuration model in Section 4 are coherent; the proof of Lemma 6 has a fixable issue in that the Steinitz ordering should be over the multiset of x_i copies of each variable, not a bijection to the set S, but the algorithm remains correct after that standard repair. The genuinely load-bearing issue is the one the reader identified: the reduction to Multiway Partitioning creates T_total - p_total dummy jobs, which are not part of the original input and can be exponential when speeds are binary. Section 5 explicitly promises a high-multiplicity implementation, but it is only a brief paragraph, and the natural-encoding claim of Theorem 1 rests on it. This does not invalidate the central idea, and the batched greedy described is very plausible, so the verdict should remain CONDITIONAL rather than REJECT. The concern is concrete and testable, but not a demonstrated counterexample to the algorithm's correctness.","tokens_in":70,"tokens_out":28022,"duration_ms":350729,"concrete_test":"Write a complete correctness proof for the Section 5 batched implementation: state the invariant that at any point in Phase II (resp. Phase III) with jobs remaining, some big machine has slack at least p_max^2 (resp. a) when counts are handled implicitly, and prove that the O(md) batching maintains it. If such a lemma cannot be proven, the natural-encoding running time of Theorem 1 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reduction in Section 4 turns makespan decision into Multiway Partitioning by adding T_total - p_total dummy jobs of size 1. When machine speeds are encoded in binary, this difference can be exponential in the input encoding length, so running the Multiway Partitioning algorithm literally makes 'n' in the running time the number of dummy jobs rather than the original n. The abstract and Theorem 1 advertise p_max^{O(d)} n^{O(1)} in the original n, so the proof must avoid materializing these dummies. Section 5 asserts that a careful high-multiplicity implementation works: the configuration ILP runs in p_max^{O(d)} m^{O(1)}, and the greedy repair is batched in O(md) steps. However, Section 5 is a sketch, not a formal theorem. In particular, it does not prove that the batched Phase II/III greedy preserves the invariants of Lemmas 3 and 4 when multiplicities are handled implicitly, and it does not specify how the configuration-IP solution is reconstructed into the O(md)-size assignment used by the greedy. Thus the central claim's natural-encoding running time is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10198,"tokens_out":30261,"duration_ms":299534,"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":[{"comment":"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.","section":"§4 (end) and §5"},{"comment":"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.","section":"§3.2, Lemma 6"}],"minor_comments":[{"comment":"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.","section":"§3.1"},{"comment":"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.","section":"Theorem 2 and Corollary 8"},{"comment":"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.","section":"§5"},{"comment":"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.","section":"§1, abstract"}],"recommendation":"major_revision","confidential_remarks":"The high-multiplicity gap is the main obstacle; I believe it is fixable and that the underlying algorithmic ideas are correct. The off-by-one in Lemma 6 is local and repairable. If the author formalizes Section 5 and corrects the Lemma 6 proof, I would support acceptance. The paper fits the scope of the journal and makes a strong contribution to exact FPT scheduling algorithms."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read on Rohwedder's paper.\n\nThe 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.\n\nWhat'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.\n\nThe 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.\n\nMinor 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.\n\nBottom 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.","headline":"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.","tokens_in":10798,"tokens_out":12756,"would_cite":true,"duration_ms":119460,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68Q27","90B35","90C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A fixed-parameter algorithm with exponent linear in the number of distinct processing times solves makespan minimization on uniform machines.","keywords":["makespan minimization","uniform machines","fixed-parameter tractability","integer programming","Steinitz lemma","multiway partitioning","high-multiplicity encoding","ETH lower bound"],"falsifier":"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.","tokens_in":9793,"feed_emoji":"⚙️","tokens_out":5619,"duration_ms":52622,"temperature":0.7,"pith_summary":"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.","feed_headline":"Makespan scheduling on uniform machines gets an ETH-tight algorithm","feed_subtitle":"Improves the exponent from quadratic to linear in the distinct job sizes, matching a known lower bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the n-fold integer programming framework whose state-of-the-art bound $p_{\\max}^{O(d^2)} n^{O(1)}$ is the baseline this paper improves","marker":"[5]"},{"why":"poses the open question about improving the exponent to $O(d)$ and establishes hardness results that frame the parameter","marker":"[14]"},{"why":"introduces the Steinitz Lemma based search-space reduction that the Multi-Choice Integer Programming algorithm builds on","marker":"[6]"},{"why":"initiated FPT algorithms for makespan scheduling with the maximum processing time as parameter","marker":"[15]"},{"why":"provides the ETH-based lower bound showing that an exponent $o(d)$ is impossible even for identical machines","marker":"[3]"},{"why":"gives a tailored integer programming approach for the case where the number of distinct speeds is polynomial in $p_{\\max}$, a special case this result generalizes","marker":"[9]"},{"why":"supplies the high-multiplicity XP algorithm for bin packing with constant item types that motivates the compact-encoding discussion","marker":"[7]"},{"why":"offers a preprocessing route via continuous relaxation and proximity results that can reduce $n$ before applying the natural-encoding algorithm","marker":"[2]"}],"fun_headline_variants":["Makespan on uniform machines: ETH-tight algorithm","Uniform machine makespan solved at optimal exponent","Linear exponent for makespan on uniform machines","Matching lower bound: uniform machine makespan algorithm","Tight makespan scheduling on uniform machines"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Makespan on uniform machines: ETH-tight algorithm","Uniform machine makespan solved at optimal exponent","Linear exponent for makespan on uniform machines","Matching lower bound: uniform machine makespan algorithm","Tight makespan scheduling on uniform machines"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000375,"raw_usage":{"total_tokens":1975,"prompt_tokens":897,"completion_tokens":1078,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":1007}},"tokens_in":513,"tokens_out":1078,"duration_ms":9998,"temperature":1.0,"reasoning_tokens":1007,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:28:04.204404+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Block-structured integer and linear program- ming in strongly polynomial and near linear time","cited_arxiv_id":null,"evidence_quote":"supplies the n-fold integer programming framework whose state-of-the-art bound $p_{\\max}^{O(d^2)} n^{O(1)}$ is the baseline this paper improves"},{"cited_title":"Complexity of sched uling few types of jobs on related and unrelated machines","cited_arxiv_id":null,"evidence_quote":"poses the open question about improving the exponent to $O(d)$ and establishes hardness results that frame the parameter"},{"cited_title":"Proximity results and faster al- gorithms for integer programming using the steinitz lemma","cited_arxiv_id":null,"evidence_quote":"introduces the Steinitz Lemma based search-space reduction that the Multi-Choice Integer Programming algorithm builds on"},{"cited_title":"Scheduling and fixed- parameter tractabil- ity","cited_arxiv_id":null,"evidence_quote":"initiated FPT algorithms for makespan scheduling with the maximum processing time as parameter"},{"cited_title":"On the optima lity of approx- imation schemes for the classical scheduling problem","cited_arxiv_id":null,"evidence_quote":"provides the ETH-based lower bound showing that an exponent $o(d)$ is impossible even for identical machines"},{"cited_title":"Improving the parameter dependency for high-multiplicity scheduling on uniform machines","cited_arxiv_id":null,"evidence_quote":"gives a tailored integer programming approach for the case where the number of distinct speeds is polynomial in $p_{\\max}$, a special case this result generalizes"},{"cited_title":"Polynomiality for b in packing with a constant number of item types","cited_arxiv_id":null,"evidence_quote":"supplies the high-multiplicity XP algorithm for bin packing with constant item types that motivates the compact-encoding discussion"},{"cited_title":"Structural Results for High-Multiplicity Scheduling on Uniform Machines","cited_arxiv_id":"2203.01741","evidence_quote":"offers a preprocessing route via continuous relaxation and proximity results that can reduce $n$ before applying the natural-encoding algorithm"}],"review_version":1}