{"id":"af093ed0-a523-4116-8878-0880bd877508","arxiv_id":"2608.00848","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"A consistency-robustness framework for robust scheduling with predictions yields constant tradeoffs for interval, budgeted and arbitrary uncertainty on the more structured machines, and provable impossibilities elsewhere.","lead":"This paper introduces a framework for robust optimization that combines a predicted scenario with the classical worst-case guarantee, balancing a single schedule's performance on both. It maps out, for makespan scheduling, exactly which machine environments and uncertainty models allow this balance with bounded loss and which do not.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; positive and negative results are internally consistent, with the min-max robustness benchmark being an explicit and analyzed scope condition.","rationale":"The reader's weakest assumption identified the benchmark choice as the main caveat. I agree this is the most important interpretive limitation, but I do not see it as a flaw in the paper's central claim because the min-max robust benchmark is part of the framework's definition and is explicitly contrasted with the learning-augmented benchmark. The proofs of the positive results are complete: Theorem 3's threshold splitting correctly handles restricted-related machines; Theorem 7's dualization correctly bounds the budgeted worst case by an interval instance with a single extra OPT_rob term; Theorem 11's block packing correctly bounds consistency by residual loads plus first-crossing overshoot and robustness by the number of blocks times OPT_rob. The lower bounds are also sound: Theorem 5's instance forces the heavy jobs onto one machine under any consistency better than 1+1/lambda; Theorem 6's single-job two-machine construction is valid for randomized algorithms via the mixing probability; Theorem 9's related-machines construction makes consistency force a slow-machine assignment and the budget then scales that assignment by L; Theorem 12's color-class construction gives the claimed expected-load lower bound. No missing proof or circular step was found. The paper is explicit about computational complexity separation and polynomial-time corollaries with black-box approximation. Thus the verdict remains ACCEPT with no adjustment.","tokens_in":40480,"tokens_out":13461,"duration_ms":164519,"concrete_test":"Recompute ThresholdSplit on the Appendix A instance with m machines and n=m^2 jobs, phat_j=1 and p+_j=m^3. For any deterministic schedule, the largest machine has at least m jobs; realize those m jobs at p+ and verify Cmax(ALG,q)/OPT(q) >= m/2. This confirms the positive tradeoffs do not extend to the standard realized-scenario benchmark, matching the paper's stated scope and the reader's flagged caveat.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the central arguments: ThresholdSplit (Theorem 3), the budget-to-interval dualization (Theorem 7), the block-packing construction (Theorem 11), and the lower bounds (Theorems 5, 6, 9, 12). The bounding steps all go through, including the first-crossing assignment (Lemma 26) and the support-function identity (Lemma 25). The only substantive caveat is that robustness is measured against OPT_rob(U), not against the realized-scenario optimum. This is stated in Definition 1 and analyzed in Appendix A, where even identical machines with interval uncertainty admit no o(m) deterministic or o(log m / log log m) randomized approximation under the alternative benchmark, with no consistency requirement. That is a genuine scope limitation: the classification does not transfer to the standard learning-augmented robustness notion. But it is not an internal inconsistency or a hidden assumption; the paper explicitly frames its contribution around the min-max robust benchmark. I therefore find no load-bearing mathematical concern that would change the verdict.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a consistency–robustness framework for robust optimization with predictions. The input is an uncertainty set U and a distinguished predicted scenario q̂ ∈ U; an algorithm must be α-consistent, i.e., near-optimal for the predicted scenario, and β-robust, i.e., competitive with the classical min-max robust optimum OPT_rob(U). The paper studies robust makespan scheduling and gives a structural classification. For interval uncertainty, ThresholdSplit achieves a (1+1/λ, 1+λ) tradeoff on restricted-related machines (Theorem 3); unrelated machines admit no constant tradeoff (Theorem 6). For budgeted uncertainty, the duality-based BudgetToInterval achieves (1+1/λ, 2+λ) on restricted assignment (Theorem 7), while related machines admit no constant tradeoff even for Γ=1 (Theorem 9). For arbitrary uncertainty, BlockPacking achieves (1+2/λ, 2λ+4) on identical machines (Theorem 11), while restricted assignment is impossible (Theorem 12). The paper also derives polynomial-time corollaries, an oblivious-budget result, a smoothness lemma, and an appendix showing that if robustness were instead measured against the realized-scenario optimum, even identical machines with interval uncertainty admit no o(m) deterministic or o(log m / log log m) randomized approximation.","tokens_in":40709,"tokens_out":34045,"duration_ms":348436,"significance":"If the results hold—and I checked the main derivations—the paper provides a clean, non-obvious diagonal classification that depends in an interesting way on the interaction between the uncertainty model and the machine environment. The techniques are genuinely useful: threshold-splitting for interval uncertainty, LP duality with a robust-optimum cutoff for budgeted uncertainty, and support-function block packing for arbitrary uncertainty. A particular strength is the transparent treatment of the robustness benchmark: Section 2 and Appendix A explicitly state that robustness is measured against OPT_rob(U), and the authors prove that the alternative learning-augmented benchmark is impossible even in very simple cases. This turns a potential scope objection into a well-documented condition. The lower-bound constants are consistent with the upper-bound tradeoffs, and the paper is careful to separate structural impossibility from computational complexity. Overall this is a substantial contribution to robust scheduling with predictions.","major_comments":[],"minor_comments":[{"comment":"The line references in the surrounding text do not match the displayed pseudocode. For example, the text says 'Line 17 assigns the tiny blocks injectively', but in the displayed algorithm the tiny-block assignment appears at line 14 and the subsequent loop starts at line 15. Please reconcile the numbering or the references.","section":"Section 5.1, Algorithm 3"},{"comment":"The pseudocode would be clearer if the loop structure were explicit: the step 'Assign the blocks in B_tiny injectively to distinct machines' should be visibly outside the preceding for-loop over i, and the later loop over i should be separated. As rendered, it is easy to misread the control flow.","section":"Section 5.1, Algorithm 3"},{"comment":"The footnote convention x/0 = 1 if x=0 and x/0 = ∞ otherwise does not cover infinite processing times for ineligible machine–job pairs in the unrelated/restricted models. Since eligibility is fixed across scenarios, one can ignore those pairs, but this should be stated explicitly.","section":"Section 2, prediction-error definition"},{"comment":"In the consistency-chain display, the factor '1/(λ s_i OPT(q^+))' is slightly ambiguous; writing '(1/s_i) ∑ ... ≤ (OPT(q̂)/(λ OPT(q^+))) · (1/s_i) ∑ p_j^+' would make the role of s_i clearer. This is purely cosmetic.","section":"Section 3.1, Theorem 3 proof"},{"comment":"The statement 'Since Γ is integral, the feasible region ... is integral' is correct but not needed for strong duality. It may help to spell out that the LP optimum equals max_{T⊆J, |T|≤Γ} ∑_{j∈T}(p_j^+ - p_j^-), which is the value used in the subsequent bound.","section":"Section 4.1, Lemma 8"}],"recommendation":"minor_revision","confidential_remarks":"The reader's assessment is fair. I find no load-bearing technical flaw in the main theorems or the lower bounds. The scope condition regarding the min-max robustness benchmark is fully disclosed and analyzed, so it should not block publication. The requested changes are editorial and local; a revised version should be acceptable without another full technical review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThis is a solid theory paper. You should know that it introduces a genuinely new framework: the prediction is not a guess at the realized scenario, it is a distinguished scenario that sets a separate benchmark. Consistency is measured against OPT(q̂), robustness against the min-max robust optimum OPT_rob(U). That is a real conceptual departure from the algorithms-with-predictions literature, and it drives the entire classification.\n\nThe positive results are technically correct as far as I checked. The threshold-splitting algorithm (Theorem 3) gives the (1+1/λ, 1+λ) tradeoff for interval uncertainty on restricted-related machines; the budget-to-interval reduction via the dual LP (Lemma 8) gives (1+1/λ, 2+λ); the support-function block construction (Theorem 11) gives (1+2/λ, 4+2λ) for arbitrary uncertainty on identical machines. I spot-checked the key inequalities and the lower-bound constructions in Theorems 5, 6, 9, and 12. They all go through. The lower bounds for unrelated machines, for related machines with a single deviating job, and for restricted assignment with arbitrary uncertainty are clean and structural.\n\nThe main soft spot is the benchmark. Robustness is defined as being within a factor of the min-max robust optimum, not of the optimal schedule for the realized scenario. That is a legitimate robust-optimization benchmark, but it is not the standard learning-augmented robustness notion. The paper's own Appendix A shows that if you take the alternative benchmark, even identical machines with interval uncertainty admit no o(m) deterministic or o(log m/log log m) randomized approximation, with no consistency requirement at all. So the positive results are conditional on this benchmark choice. The authors are upfront about it, and it does not make the proofs wrong, but it does cap the significance: this is a contribution to robust scheduling with predictions, not to algorithms with predictions in the usual sense.\n\nA second, minor caveat: the algorithms use exact optimization subroutines. The polynomial-time versions carry extra γ factors. That is a reasonable separation, but readers should not expect clean poly-time constants.\n\nWho benefits: anyone working on robust optimization with forecasts, scheduling under uncertainty, or learning-augmented algorithms. It deserves a serious referee. I would send it to review and likely accept after minor revisions.\n\nBest","headline":"A structurally interesting paper with a new framework and complete proofs; the robustness benchmark is a real scope limitation, but it is explicit and honestly analyzed.","tokens_in":41178,"tokens_out":2421,"would_cite":true,"duration_ms":29067,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W40","90B35","68W25","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"A complete consistency-robustness map for robust makespan scheduling: six of twelve uncertainty-machine combinations admit constant tradeoffs, the rest are impossible.","keywords":["robust optimization","algorithms with predictions","consistency-robustness tradeoff","makespan scheduling","interval uncertainty","budgeted uncertainty","min-max robust optimum","learning-augmented algorithms"],"falsifier":"Run the hard instance of Theorem 5 with m=3, λ=2, L=10: two jobs have (p̂,p⁺)=(1/2,10) and two have (1,1). The theorem says every deterministic schedule with predicted makespan below 1.5 has worst-case makespan at least 2·OPT(q⁺)=20. A schedule with predicted makespan 1.4 and worst-case makespan 19 on this instance would refute the claimed tightness; observing that ThresholdSplit itself returns worst-case 20 would confirm it.","tokens_in":40387,"feed_emoji":"⚖️","tokens_out":9201,"duration_ms":102549,"temperature":0.7,"pith_summary":"The paper introduces a framework for robust optimization with predictions: the input names an uncertainty set and a predicted scenario, and a single schedule must be both consistent (near-optimal for the predicted scenario) and robust (competitive with the classical min-max robust optimum). For robust makespan scheduling, it delivers a complete classification: constant tradeoffs are achievable exactly for interval uncertainty on identical, restricted, and related machines; budgeted uncertainty on identical and restricted machines; and arbitrary uncertainty on identical machines. Each positive cell comes with an explicit tunable tradeoff, and each negative cell is proved impossible even for randomized algorithms. The diagonal pattern shows that combining predictions with robustness depends jointly on how expressive the uncertainty model is and how symmetric the machine environment is. If the framework and classification are right, they give a principled way to decide where learned predictions can be safely used in robust scheduling.","feed_headline":"Six of twelve robust scheduling setups allow constant tradeoffs","feed_subtitle":"Predictions and worst-case guarantees coexist for six uncertainty-machine combinations; the rest are provably impossible.","key_machinery":"Three constructions carry the argument. (1) ThresholdSplit: for interval uncertainty, the worst case is the single upper-endpoint scenario, so each job is compared by its normalized contribution to the predicted optimum versus the robust optimum; jobs relatively heavy in the worst case are scheduled under the robust scenario, the rest under the predicted scenario, and the two schedules merged machine by machine—yielding (1+1/λ, 1+λ). (2) BudgetToInterval: for budgeted uncertainty, the worst load of any job set is dualized into a global cutoff term plus an effective interval instance with sizes p⁻ + (p⁺ − p⁻ − τ)₊, where τ = OPT_rob/Γ—yielding (1+1/λ, 2+λ). (3) BlockPacking: for arbitrary unc","core_discovery":"The central claim is a structural dichotomy for robust makespan scheduling with predictions. For each uncertainty model (interval, budgeted, arbitrary) and each machine environment (identical, restricted, related, unrelated), either every λ>0 admits a deterministic algorithm with consistency 1+O(1/λ) and robustness O(λ) against the min-max robust optimum, or no instance-independent constants exist. The positive cells are interval-identical/restricted/related, budgeted-identical/restricted, and arbitrary-identical; the remaining six combinations are impossible, sometimes already with one job on two machines or one deviating job. The paper also proves the tradeoff's linear dependence on λ is a","pith_inferences":["Editorial inference: the three impossibility proofs all work by having the adversary single out a machine or color class, suggesting that the real boundary is whether the uncertainty set can express correlations that break the symmetry the algorithm relies on; other machine models with limited symmetry may fall on the impossible side.","Editorial inference: the budget-to-interval dualization, which selects a cutoff from the robust optimum, appears reusable as a general reduction for min-max budgeted scheduling even without predictions, converting a budgeted instance into an interval instance at a small constant loss.","Editorial inference: BlockPacking uses only monotonicity and subadditivity of Ψ_U, so for identical machines the construction should work with any oracle that estimates Ψ_U within a constant factor, not necessarily an explicit uncertainty set; the paper does not develop this oracle-perspective.","Editorial inference: the diagonal classification suggests a pragmatic design rule—invest in learning-augmented schedules when the uncertainty model is structured or machines are symmetric; expect impossibility when the uncertainty is expressive and machines are heterogeneous."],"forward_implications":["For interval uncertainty on identical, restricted-assignment, and related machines, one algorithm gives a smooth Pareto curve: setting λ=1 yields schedules that are 2-competitive on the prediction and 2-competitive on the worst case.","Unrelated machines admit no constant tradeoff even for one job on two machines, so no instance-independent constants exist there under any λ.","For budgeted uncertainty, restricted assignment retains a constant tradeoff even though the adversary's choice of deviating jobs depends on the schedule; related machines fail already at budget Γ=1.","For arbitrary uncertainty, identical machines are the only environment with a constant tradeoff; restricted assignment fails because the adversary can correlate deviations across color classes.","Any α-consistent algorithm is automatically η²α-smooth under prediction error η, so the consistency guarantee degrades gracefully rather than abruptly as the prediction worsens."],"supporting_citations":[{"why":"Introduces the interval/box uncertainty model that forms the base case of the classification.","marker":"[Soy73]"},{"why":"Introduces cardinality-budgeted (Γ-)uncertainty, the second uncertainty model studied.","marker":"[BS04]"},{"why":"Supplies the classical min-max robust optimization benchmark against which robustness is measured.","marker":"[KY97]"},{"why":"Provides the approximation algorithms for budgeted robust makespan that serve as black boxes in polynomial-time versions and as benchmarks for lower-bound comparisons.","marker":"[Bou+21]"},{"why":"Provides the 2-approximation for unrelated-machine makespan used to make ThresholdSplit polynomial-time in the interval case.","marker":"[LST90]"},{"why":"Supplies the fixed-dimensional vector-scheduling PTAS used for an alternative polynomial-time implementation on identical machines under interval uncertainty.","marker":"[CK04]"},{"why":"Initiates the learning-augmented consistency-robustness paradigm that the paper adapts to robust optimization with a separate predicted-scenario benchmark.","marker":"[L V21]"}],"fun_headline_variants":["Scheduling with predictions: exactly 6 of 12 cases allow constants","Robust scheduling with predictions: half the combos work, half impossible","Predictions and robustness in scheduling: 6 positive, 6 negative results","Robust scheduling tradeoff: a complete dichotomy with predictions","Exactly half of robust scheduling setups allow constant tradeoffs"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that 'robust' means competitive with the best schedule chosen before knowing which scenario occurs (the min-max robust optimum); if 'robust' instead meant competitive with the optimal schedule for whichever scenario actually happens, the paper's own Appendix A shows even identical machines with interval uncertainty would admit no useful approximation, so the whole classification is conditional on that benchmark choice.","fun_headline_variants_meta":{"raw":{"variants":["Scheduling with predictions: exactly 6 of 12 cases allow constants","Robust scheduling with predictions: half the combos work, half impossible","Predictions and robustness in scheduling: 6 positive, 6 negative results","Robust scheduling tradeoff: a complete dichotomy with predictions","Exactly half of robust scheduling setups allow constant tradeoffs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000569,"raw_usage":{"total_tokens":2573,"prompt_tokens":830,"completion_tokens":1743,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":1653}},"tokens_in":574,"tokens_out":1743,"duration_ms":14086,"temperature":1.0,"reasoning_tokens":1653,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T00:11:18.600630+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the hard instance of Theorem 5 with m=3, λ=2, L=10: two jobs have (p̂,p⁺)=(1/2,10) and two have (1,1). The theorem says every deterministic schedule with predicted makespan below 1.5 has worst-case makespan at least 2·OPT(q⁺)=20. A schedule with predicted makespan 1.4 and worst-case makespan 19 on this instance would refute the claimed tightness; observing that ThresholdSplit itself returns worst-case 20 would confirm it.","supporting_citations":[],"review_version":1}