{"id":"904ee99d-63c5-4f64-80fd-6e0859f7455f","arxiv_id":"2608.12224","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The authors improve exact algorithms for P||ΣwjCj to O(2.755^n), for P||ΣwjUj to O*(2^n), and, assuming the Asymptotic Rank Conjecture, for Bin Packing to O((2-ε)^n).","lead":"This paper presents faster exact algorithms for two classical multi-machine scheduling problems, improving the baselines from 3^n to 2.755^n for weighted completion time and to 2^n for weighted tardy jobs. It also shows, under the Asymptotic Rank Conjecture, that Bin Packing can be solved faster than the classic 2^n barrier.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The load-bearing concern is the unproved no-false-positives claim for the fixed-bin algorithm in Lemma 6; if false, the combined Bin Packing procedure can return Yes on a No-instance.","rationale":"The scheduling results (Theorems 1–3) are well supported: the DP recurrences follow from Lemma 10, the base cases via meet-in-the-middle and LP queries are coherent, and the running-time analyses are correct. The weighted tardy jobs result (Theorem 2) is also sound. For Bin Packing, the four-case disjunction is exhaustive, and Lemmas 21, 23, and 24 have explicit no-false-positives arguments. The only unsupported load-bearing premise is the no-false-positives property attributed to [35] in Lemma 6. The paper itself notes that the cited theorem does not state this property. Since the combined algorithm's correctness on No-instances depends on it, this is the right condition for acceptance: supply a proof or precise citation, or adjust the theorem to a one-sided-error statement. The reader's conditional verdict is appropriate; no change recommended.","tokens_in":34486,"tokens_out":42907,"duration_ms":354141,"concrete_test":"Inspect the proof of [35, Theorem 1.1] and the algorithm it describes; determine whether any Yes output is accompanied by an explicit packing certificate, or whether the randomized steps (e.g., hashing, polynomial evaluation) can produce a Yes without a witness. If no certificate is guaranteed, run the subroutine on small No-instances (e.g., 8 items, 3 bins, capacity chosen so no packing exists) over many random seeds to see if a false positive occurs; alternatively, provide a formal argument that the output cannot be Yes on a No-instance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4's decision procedure outputs No only if all four case algorithms output No. Lemma 22 (Case B) returns Yes whenever it finds X∈W with BP[m−6,X]=0 and the Lemma 6 subroutine declares I\\X packable into 6 bins. The correctness of this No/No inference rests entirely on the claim, inserted after Lemma 6, that the randomized algorithm of [35, Theorem 1.1] \"has no false positives\". The paper admits the cited theorem does not state this and provides no proof or certificate argument. If the subroutine can return Yes on a No-instance, Lemma 22 inherits that false positive and the combined algorithm can answer Yes on an infeasible instance, invalidating Theorem 4 even under ARC. Lemmas 21, 23, and 24 each explicitly construct a valid packing from any Yes answer, so this is the only place where negative-instance correctness is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper gives exact exponential algorithms for two multi-machine scheduling problems and a conditional algorithm for Bin Packing. It claims P||Σw_jC_j can be solved in O(2.755^n) time, with further improvements O(2.389^n), O(2.726^n), and O(2.733^n) for 4, 5, and 6 machines, and P||Σw_jU_j in O*(2^n) time. The scheduling algorithms use dynamic programming whose base cases are solved by meet-in-the-middle with a linear-programming-query data structure (for weighted completion time) and by Fast Subset Convolution plus Moore's algorithm (for tardy jobs). The Bin Packing section, under the Asymptotic Rank Conjecture, claims an O((2−ε)^n) decision procedure based on a four-case analysis that combines a fixed-constant-bin packing subroutine and a 3-way Partitioning subroutine.","tokens_in":34702,"tokens_out":50894,"duration_ms":453264,"significance":"The scheduling results are clear algorithmic improvements over the O*(3^n) baseline, and the proofs appear technically sound; the recurrences, entropy bounds, and case analyses are written out in detail. Theorem 3's fixed-machine bounds are additional useful contributions. The Bin Packing result, if fully supported, would be a substantial advance under ARC, and the paper clearly labels the ARC assumption. However, I cannot endorse Theorem 4 as written because the claimed no-false-positives property of the cited constant-bin algorithm is load-bearing and unproved; this is a correctness gap, not a presentation issue. The scheduling sections are independent of the Bin Packing section and appear publishable on their own.","major_comments":[{"comment":"The assertion that the algorithm of [35, Theorem 1.1] 'has no false positives' is load-bearing and currently unsupported. The manuscript itself notes that the cited theorem does not state this property, and no proof or certificate argument is supplied. Lemma 22 uses this property to conclude that the Case B test never accepts an infeasible instance: the test accepts only if for some X∈W both BP[m−6,X]=0 and the Lemma 6 subroutine reports that I\\X packs into 6 bins, and the 'No' direction of Lemma 22 is exactly the contrapositive of that implication. Moreover, Lemma 22 calls the subroutine for all 2^{H(ε)n} members of W, so a per-call false-positive probability of 1/poly(n) would be amplified and cannot be absorbed by a union bound. Theorem 4's final sentence 'none of the four algorithms have false positives' inherits this gap. I recommend proving the no-false-positives property directly from [35], or replacing the subroutine with one that returns a verifiable packing, or with an algorithm whose false-positive probability is exponentially small and explicitly accounted for in the analysis.","section":"Section 6, Lemma 6"}],"minor_comments":[{"comment":"The statement says the table entries are returned for i∈[m], but Lemma 23 (and the m=6 case of Lemma 22) needs BP[0,·]; the proof initializes the i=0 row, so the statement should read i∈{0}∪[m].","section":"Lemma 20"},{"comment":"The constant from Lemma 6 is typeset as 'ε6' and sometimes as 'ε^6'; use ε_6 to avoid confusion with the small constant ε.","section":"Lemma 22 and Theorem 4"},{"comment":"The number of sampled sets, 2^{(1−ε)n}n^2, may not be an integer; state that a ceiling or rounding is used. This does not affect the high-probability claim.","section":"Lemma 23"},{"comment":"In the discussion of reconstructing a packing from a decision oracle, the trivial case 'm=n' should read 'm≥n', since m>n items can also be placed in distinct bins.","section":"Section 6, solution reconstruction"},{"comment":"In the correctness proof, 'we found S1,S2,S3' should be phrased in terms of existence, since Lemma 7 is stated as a decision procedure; a standard self-reduction can supply witnesses if construction is needed.","section":"Lemma 24"},{"comment":"Lemma 23 is stated with success probability only 1/2; the proof of Theorem 4 should say explicitly that this is boosted to 1−n^{−Ω(1)} before the four algorithms are combined.","section":"Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The scheduling sections are independent of the Bin Packing section and appear technically sound. The main risk is the unsupported no-false-positives assertion for [35]'s constant-bin algorithm; if the authors can prove it, or supply a certified subroutine, the Bin Packing result becomes credible. I see no circularity or novelty disclosure problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The scheduling half of this paper is strong and delivers what it promises. The O(2.755^n) algorithm for P||ΣwjCj is a real improvement over Lenté et al.'s O*(3^n), and the combination of meet-in-the-middle with the LP-query data structure is a fresh and effective idea. The O*(2^n) bound for P||ΣwjUj via fast subset convolution and Moore's algorithm is clean, and the extra results for fixed m (the 2.389^n bound for m=4, in particular) are a nice bonus. I checked the recurrences, the entropy calculations, and the case analyses in Lemmas 9-16 and 21-24; everything there is coherent. The proofs in Section 4 and Section 5 look correct to me.\n\nThe soft spot is exactly where the reader put it: Lemma 6. The paper says after the lemma that [35, Theorem 1.1] \"does not state that the algorithm has no false positives, but this is indeed the case\" — and then uses that property as a load-bearing component of Lemma 22 and Theorem 4. The stress test is right: if the fixed-bin subroutine can return Yes on a No-instance, then the combined bin-packing procedure can output Yes on an infeasible instance, even under ARC. This is not a matter of style; it's a correctness gap in the conditional theorem as written. It may well be patchable, either by proving the property or by quoting a precise theorem from [35], but as it stands the claim is unsupported. That's the one thing I would insist on before accepting.\n\nTwo smaller notes. First, the paper should state the running time of reference [21] relative to the new scheduling bounds; if that work already improves over 3^n, the comparison should be explicit. Second, the randomized part of Case C is handled carefully, with the sampling probability and the DP setup consistent; I have no issue there.\n\nOverall: the scheduling part is a genuine advance, and the bin-packing part is an interesting and mostly well-argued conditional result with one fixable gap. This deserves serious refereeing. I would send it out, and I would recommend conditional acceptance on the strength of the scheduling theorems alone, with the Lemma 6 issue resolved before publication.","headline":"The scheduling results are solid and genuinely new; the conditional bin-packing theorem is clever but rests on an unproved no-false-positives claim that must be fixed before the result can be trusted as stated.","tokens_in":35251,"tokens_out":5544,"would_cite":true,"duration_ms":49519,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W40","90B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that weighted completion-time scheduling can be solved in $O(2.755^n)$ time and weighted tardy-job scheduling in $O^*(2^n)$ time, and that, assuming the Asymptotic Rank Conjecture, Bin Packing can be solved in…","keywords":["scheduling","exact exponential-time algorithms","multi-machine scheduling","weighted completion time","tardy jobs","bin packing","asymptotic rank conjecture","meet-in-the-middle"],"falsifier":"For all Bin Packing instances with up to 20 items and between 7 and 10 bins, run the four-case algorithm and an exact $O^*(2^n)$ dynamic program; if the four-case procedure says Yes on any instance where the exact DP says No, then the no-false-positives claim behind Lemma 6 is false and Theorem 4's soundness collapses. A faster preliminary check is to run the Lemma 6 subroutine alone on all six-bin subinstances generated during Case B and compare its answers with exact packing.","tokens_in":34296,"feed_emoji":"⏱️","tokens_out":12471,"duration_ms":112382,"temperature":0.7,"pith_summary":"This paper is about the exact exponential-time complexity of two fundamental multi-machine scheduling problems and of their common relative, Bin Packing. Its central claim is that $P\\mid\\mid \\sum w_j C_j$ can be solved in $O(2.755^n)$ and $P\\mid\\mid \\sum w_j U_j$ in $O^*(2^n)$, improving the previous $O^*(3^n)$ algorithms. It further claims that, assuming the Asymptotic Rank Conjecture, Bin Packing can be solved in $O((2-\\varepsilon)^n)$ for some constant $\\varepsilon>0$, breaking the classic $O^*(2^n)$ barrier. A reader should care because these are benchmark NP-hard problems: each improvement in the base of the exponential is a step toward understanding how hard exact optimization on identical machines really is, and the Bin Packing result conditionally settles a long-standing open question. The methods are combinations of meet-in-the-middle, linear-programming query data structures, fast subset convolution, and a cardinality-based case analysis.","feed_headline":"Scheduling drops below the 3^n time barrier","feed_subtitle":"Weighted completion and tardy jobs beat 3^n; bin packing beats 2^n under the tensor-rank conjecture.","key_machinery":"The load-bearing identity is the recurrence of Lemma 10: for any split of $i$ machines into $j$ and $i-j$, the optimum $\\mathrm{OPT}(i,S)$ equals $\\min_{S'\\subseteq S,\\, |S'|\\le j|S|/i}\\{\\mathrm{OPT}(j,S')+\\mathrm{OPT}(i-j,S\\setminus S')\\}$, because in an optimal schedule the $j$ machines with the fewest jobs contain at most $j|S|/i$ jobs. This turns the naive $3^n$ enumeration of subsets into enumeration over subsets of size at most a constant fraction, whose count is bounded by $2^{H(\\alpha)n}$; the base cases for $m\\le 3$ are handled by a meet-in-the-middle scheme that encodes each half-partition as a point and answers the min-over-partitions query with a 2- or 3-dimensional linear-programming data structure. For $P\\mid\\mid \\sum w_j U_j$, the same recurrence is evaluated with Min-Plus Subset Convolution, and the single-machine base case is the polynomial-time algorithm of [32]. For Bin Packing, the machinery is the four-case cardinality split together with a subset-sum DP table $\\mathrm{BP}[i,S]$ and, in Case D, a reduction to $3$-way Partitioning for $(1-\\varepsilon)/2$-bounded set families, solved under ARC.","core_discovery":"On the paper's own terms, the discovery is a pair of exact algorithms and one conditional algorithm. Theorem 1 gives $O(2.755^n)$ for minimizing total weighted completion time on identical parallel machines; Theorem 2 gives $O^*(2^n)$ for the weighted number of tardy jobs; Theorem 3 refines the completion-time bound for fixed small machine counts; Theorem 4 states that under the Asymptotic Rank Conjecture there is a constant $\\varepsilon>0$ for which Bin Packing on $n$ items can be decided with high probability in $O((2-\\varepsilon)^n)$ time. The scheduling algorithms use a dynamic program whose transition only needs to split off a subset of size at most a fixed fraction of the current job set, with base cases for two and three machines accelerated by meet-in-the-middle and a data structure for linear programming queries; the tardy-jobs algorithm uses fast subset convolution over the DP transitions. The Bin Packing algorithm partitions all possible solutions into four cases according to how many items lie in the largest bins, and solves each case by subset-sum DP, the constant-bin algorithm, random sampling, or a reduction to 3-way Partitioning, the last being the only ARC-dependent ingredient.","pith_inferences":["The no-false-positives premise behind Lemma 22 is testable in isolation: the six-bin subroutine could be compared against exact DP on small random instances, and any violation would require a different constant-bin subroutine for Theorem 4.","The four-case cardinality split is a template that likely transfers to other packing and scheduling problems: classify feasible solutions by how items distribute across bins, then attack each class with the cheapest available sub-$2^n$ oracle.","The unbalanced split $\\alpha\\approx0.628$ for $m=4$ illustrates that when preprocessing and query costs are asymmetric, the optimal meet-in-the-middle split is not half-half; similar trade-off analysis could improve other LP-query-based DPs."],"forward_implications":["For $P\\mid\\mid \\sum w_j C_j$, the previous $O^*(3^n)$ bound improves to $O(2.755^n)$, giving the first known algorithm with base below 3 for this problem.","For $P\\mid\\mid \\sum w_j U_j$, the bound improves to $O^*(2^n)$, matching the classic inclusion-exclusion bound for Bin Packing.","For fixed machine counts, the constant-base bounds improve further: $O^*(m^{n/2})$ for $m\\le 3$, and $O(2.389^n)$, $O(2.726^n)$, $O(2.733^n)$ for $m=4,5,6$.","Assuming ARC, Bin Packing admits a randomized $O((2-\\varepsilon)^n)$-time decision procedure, conditionally resolving an open question.","A SETH-based lower bound ruling out $O^*((2-\\varepsilon)^n)$ Bin Packing would imply that SETH and ARC are not both true, so the result forms a barrier against such a lower bound."],"supporting_citations":[{"why":"Supplies the O*(3^n)-time baseline for both scheduling problems, which Theorems 1 and 2 improve.","marker":"[30]"},{"why":"Provides the 2- and 3-dimensional linear-programming query data structure used to compute base cases for m=2 and m=3 machines.","marker":"[19]"},{"why":"Provides the fast subset convolution used in the DP transitions for P||ΣwjUj.","marker":"[3]"},{"why":"Provides the polynomial-time algorithm that computes the single-machine base case for P||ΣwjUj.","marker":"[32]"},{"why":"Supplies the faster-than-2^n algorithm for Bin Packing with a constant number of bins, used in Case B and Lemma 6, and the sampling inspiration for Case C.","marker":"[35]"},{"why":"Supplies the ARC-based O*(2^{(1-ηε)n}) algorithm for 3-way Partitioning used in Case D.","marker":"[2]"},{"why":"Supplies the single-machine sorting rule for weighted completion time, used to compute cost(X) in the meet-in-the-middle schemes.","marker":"[40]"}],"fun_headline_variants":["Scheduling algorithms break 3^n time barrier","Exact scheduling improves to 2.755^n and 2^n","Tardy jobs scheduling now in 2^n time","Bin packing under ARC: faster than 2^n","Multi-machine scheduling drops below 3^n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Bin Packing result depends on the fixed-bin subroutine never saying Yes on an unpackable instance, a property that the cited theorem does not state and that the paper asserts as \"indeed the case.\"","fun_headline_variants_meta":{"raw":{"variants":["Scheduling algorithms break 3^n time barrier","Exact scheduling improves to 2.755^n and 2^n","Tardy jobs scheduling now in 2^n time","Bin packing under ARC: faster than 2^n","Multi-machine scheduling drops below 3^n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001291,"raw_usage":{"total_tokens":5359,"prompt_tokens":1121,"completion_tokens":4238,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":4161}},"tokens_in":737,"tokens_out":4238,"duration_ms":30640,"temperature":1.0,"reasoning_tokens":4161,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:14:00.011764+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For all Bin Packing instances with up to 20 items and between 7 and 10 bins, run the four-case algorithm and an exact $O^*(2^n)$ dynamic program; if the four-case procedure says Yes on any instance where the exact DP says No, then the no-false-positives claim behind Lemma 6 is false and Theorem 4's soundness collapses. A faster preliminary check is to run the Lemma 6 subroutine alone on all six-bin subinstances generated during Case B and compare its answers with exact packing.","supporting_citations":[{"cited_title":"Exponential algorithms for scheduling problems","cited_arxiv_id":null,"evidence_quote":"Supplies the O*(3^n)-time baseline for both scheduling problems, which Theorems 1 and 2 improve."},{"cited_title":"Guibas, Jorge Stolfi, and Kenneth L","cited_arxiv_id":null,"evidence_quote":"Provides the 2- and 3-dimensional linear-programming query data structure used to compute base cases for m=2 and m=3 machines."},{"cited_title":"Michael Moore","cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time algorithm that computes the single-machine base case for P||ΣwjUj."}],"review_version":1}