{"id":"29f9e429-3202-4e00-90e9-cdcfa5ef6da1","arxiv_id":"2411.17245","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Under the one-step smoothed model with densities bounded by φ, the expected number of iterations to a k-swap local optimum is O(m^2 n^{2k+2} log m φ).","lead":"This paper proves a polynomial smoothed upper bound on the number of improvement steps the k-swap local search takes to reach a local optimum in identical-machine makespan scheduling. The result explains why the exponential worst-case example from the authors' earlier work is rare once job processing times are slightly randomized.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 3.3's O(m n^k) type-1 bound rests on an unstated charging of each improving swap to a fixed rank-ℓ tuple; without an explicit proof that the same (A,B) cannot recur at a different rank, Theorem 3.11 is not fully established.","rationale":"The reader's weakest assumption names exactly the link I find load-bearing: the type-1 charging in Corollary 3.3. I agree that this is the least explicit step, and that Theorem 3.11 cannot stand if it fails. I also checked the rest of the chain. The type-2 potential argument (Lemma 3.7 and Corollary 3.8) is internally consistent: the decrease is at least 4δmin, and Φ(1) ≤ 2mn. The tail-sum step in Theorem 3.11 is correct: T is bounded by the number of schedules m^n, and summing H_{m^n} = n log m gives the stated O(m^2 n^{2k+2} log m φ). Lemma 3.10's equality is false as written, but replacing it by the inequality P(|p(A)−p(B)| ≤ α) ≤ 2αφ is sufficient and valid for densities bounded by φ, so it does not threaten the central claim. The missing charging argument appears repairable: the key observation, not stated in the paper, is that once a machine enters γl it can never be the target of an improving swap (its gap to any critical machine is < δmin while every improving swap amount is ≥ δmin), which keeps the load of the machine carrying A frozen until it becomes critical. If this observation is inserted, Lemma 3.2's conclusion can be made rigorous. Because the concern is about exposition and completeness of the proof rather than a demonstrated false statement, I do not move the verdict: it remains conditional on supplying the charging argument.","tokens_in":9315,"tokens_out":34600,"duration_ms":315986,"concrete_test":"Re-derive Corollary 3.3 with an explicit charging rule: for each type-1 iteration, let ℓ be the rank of the non-critical machine in nondecreasing load order, and prove that the tuple (A,B,ℓ) cannot recur before a type-2. The missing step is to show that when A later lies on a critical machine and B on the ℓ-th smallest machine, Lmax − Lℓmin ≤ p(A) − p(B); use the invariant that a machine in γl cannot be the target of an improving swap because any swap amount is at least δmin while the gap from any critical machine is less than δmin. If this derivation cannot be completed, search for a small counterexample (e.g., k=2, m=4, drawn from a fine grid of processing times) in which the same ordered pair (A,B) is swapped with two different target ranks before any type-2 move; such an instance would falsify Corollary 3.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The smoothed bound in Theorem 3.11 is built on the deterministic bound O(m^2 n^{k+1}/δmin) of Corollary 3.9, and Corollary 3.9 inherits its type-1 count O(m n^k) from Corollary 3.3. Corollary 3.3 is justified only by counting \"different combinations of A, B, and ℓ\" after Lemma 3.2. Lemma 3.2, however, is proved for one fixed rank ℓ: it shows that after swapping A with B out of the ℓ-th smallest machine, the same pair cannot subsequently be swapped into the ℓ-th smallest machine. The paper does not state explicitly that every type-1 swap is charged to the rank ℓ of its actual non-critical target, and it does not rule out the same sets (A,B) reappearing with a different rank ℓ′ before a type-2 occurs. Since a type-1 swap can target any machine in γs, and since the gap Lmax − Lℓmin for a lower-ranked machine can be larger than for the original ℓ, the proof as written does not control that possibility. If the same (A,B) could recur at a different rank, the number of distinct tuples would not bound the number of type-1 moves, and both Corollary 3.9 and Theorem 3.11 would collapse. The false equality in Lemma 3.10 is also a defect, but it is not load-bearing because only the inequality P(|p(A)−p(B)| ≤ α) ≤ 2αφ is needed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper analyzes the k-swap local search neighborhood for identical parallel machine makespan scheduling (P||Cmax) under the one-step smoothed analysis model. The main result is an upper bound of O(m^2 n^{2k+2} log m φ) on the expected number of iterations required to reach a k-swap local optimum, where the processing times are drawn independently from density functions bounded by φ. The proof splits improving k-swaps into two types, bounds the number of consecutive type-1 swaps by O(m n^k) using a rank-based charging argument, bounds the total number of type-2 swaps by O(m n / δmin) using a pairwise load-difference potential, and then controls the probability that δmin is small via a union bound over job subsets. The paper is self-contained and gives an explicit deterministic bound before applying the probabilistic argument.","tokens_in":32,"tokens_out":25652,"duration_ms":330920,"significance":"The result is a useful contribution: it provides a rigorous smoothed-analysis explanation for why the exponential worst-case lower bound for k ≥ 3 (from the authors' earlier work) is not observed in typical instances. The deterministic decomposition into type-1 and type-2 swaps is natural, the potential function for type-2 swaps is clean, and the overall proof strategy is coherent. The bound is explicit and does not rely on any fitted parameters or circular reasoning; the citation to the authors' previous lower bound is used only as motivation. The main issues are presentational and local, but one of them (the upper limit of the summation in Theorem 3.11) affects the proof of the stated bound and must be corrected.","major_comments":[{"comment":"The proof writes E(T) = sum_{t=1}^{mn} P(T ≥ t), but the text says the expectation is bounded by the number of different schedules, which is m^n. Summing only to mn is not an upper bound on E(T), since E[T] = sum_{t=1}^{m^n} P(T ≥ t) and the omitted tail is nonnegative. This is load-bearing: with the upper limit m^n, the harmonic sum is O(n log m) and the displayed final bound follows; with the upper limit mn, the displayed equality does not prove the theorem. Please correct the upper limit and carry the constant from Corollary 3.9 through the inequality involving δmin.","section":"Theorem 3.11, proof (final displayed equation)"},{"comment":"The counting argument should explicitly define the charging: each type-1 swap in a consecutive sequence is charged to the tuple (A, B, ℓ), where ℓ is the rank of the target machine i' in the sorted load order of γs at the start of the iteration. Lemma 3.2 shows that after such a swap, the gap Lmax − Lℓmin remains at most p(A) − p(B) for the rest of the type-1 sequence, so the same tuple cannot be charged again; recurrence of the same (A, B) at a different rank ℓ' would be a different tuple and is handled by the m factor. As written, the proof jumps from counting 'combinations of A, B, and ℓ' to the bound without stating the injectivity, which makes the argument appear to have a gap. Please make this charging explicit.","section":"Corollary 3.3 and Lemma 3.2"}],"minor_comments":[{"comment":"The proof states P(|p(A) − p(B)| ≤ α) = 2αφ; this equality is false in general. The correct statement is the upper bound P(|p(A) − p(B)| ≤ α) ≤ 2αφ, which follows because the density of |p(A) − p(B)| is bounded by φ. The union bound then yields the lemma.","section":"Lemma 3.10"},{"comment":"The constant from Corollary 3.9 is dropped: Corollary 3.9 gives T ≤ C m^2 n^{k+1}/δmin for some constant C, so P(T ≥ t) should be bounded by P(δmin ≤ C m^2 n^{k+1}/t). Please carry the constant or state that it is absorbed in the O-notation.","section":"Theorem 3.11 proof"},{"comment":"The proof writes 'i′ ∈ γℓ(t + 1)' where γℓ is not defined; this should be γl.","section":"Lemma 3.2"},{"comment":"When |γs(t+1)| < ℓ, the quantity Lℓmin(t+1) is the ℓ-th smallest load among all machines, not necessarily in γs, and the inequality Lℓmin(t′) ≥ Lℓmin(t+1) is not covered by Lemma 3.1. In that case the tuple (A, B, ℓ) cannot recur because no γs machine has rank ℓ later, so the conclusion still holds, but the proof should address this case explicitly.","section":"Lemma 3.2"},{"comment":"The step from sum_{t=1}^{m^n} 1/t to O(m^2 n^{2k+2} log m φ) uses log(m^n) = O(n log m); please add this justification.","section":"Theorem 3.11 proof"},{"comment":"The phrase 'ℓmin-load machine' is used both for a machine with a fixed rank ℓ and for the general notion of a non-critical machine. Please clarify that in Lemma 3.2 the rank ℓ is fixed to the rank of the target machine at the start of the current type-1 swap.","section":"Section 3, definition of ℓmin-load machine"}],"recommendation":"major_revision","confidential_remarks":"The paper is essentially correct in its central claim, and the deterministic bound appears sound after the charging argument in Corollary 3.3 is made explicit. The main issue is the summation upper limit in Theorem 3.11: as written it is mn, but the proof's own justification ('number of different schedules') requires m^n. This is likely a typo, but it is load-bearing because the displayed derivation does not otherwise establish the stated expectation bound. With that correction and a few clarifying sentences, the paper should be suitable for publication. The self-citation to [31] is used appropriately as motivation, not as an input to the proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis is a solid smoothed analysis of k-swap local search for identical-machine makespan scheduling. The main theorem, E[T] = O(m^2 n^{2k+2} log m φ), is new and the proof largely checks out. The type-1/type-2 decomposition and the potential function for type-2 moves are genuine contributions; the rank-based counting for type-1 moves is the nontrivial step and is sound.\n\nThe soft spots are presentation, not mathematics. Lemma 3.10 states an equality where only an inequality holds: P(|p(A)-p(B)| ≤ α) ≤ 2αφ. The density of the difference is at most φ, so the inequality is what the proof needs; the equality is false but harmless. Corollary 3.3 is too terse: the charging argument should say explicitly that each type-1 swap is charged to the triple (A,B,ℓ), where ℓ is the rank of the target at that time, and Lemma 3.2 shows that triple cannot repeat before a type-2. The stress-test worry that the same (A,B) could recur at a different rank is not a real gap—that would be a different triple, and the m factor already covers it. Third, the proof of Theorem 3.11 sums to mn, which must be a typo for m^n. The maximum number of iterations is at most the number of schedules, m^n, and the harmonic sum to m^n is n log m, giving exactly the stated bound. As printed, the bound doesn't follow; with this correction it does.\n\nThe self-citation to the authors' lower bound [31] is motivation only, not an input; no circularity. The result is significant for the scheduling and local search community, and it deserves a serious referee. The fixes are straightforward: replace the equality with an inequality, spell out the charging in Corollary 3.3, and correct the upper limit in the tail sum.\n\nRecommendation: send to peer review. I'd be happy to read the revision.\n\nBest","headline":"Solid smoothed analysis of k-swap local search for makespan scheduling; main theorem holds, with fixable presentation issues.","tokens_in":10151,"tokens_out":16846,"would_cite":true,"duration_ms":133426,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W40","90B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Under random perturbation of processing times, k-swap local search reaches a local optimum in polynomially many expected iterations whenever k is constant.","keywords":["smoothed analysis","local search","k-swap neighborhood","makespan scheduling","identical parallel machines","iterative improvement","P||Cmax"],"falsifier":"Exhibit a sequence of consecutive type-1 swaps in which the same pair of job sets is swapped while the least-loaded machine has the same rank more than once, with no type-2 swap in between. Lemma 3.2 says such a repetition is impossible; finding one would invalidate Corollary 3.3 and collapse the deterministic $O(m^2 n^{k+1}/\\delta_{\\min})$ bound and its smoothed consequence.","tokens_in":9101,"feed_emoji":"🎲","tokens_out":9105,"duration_ms":79929,"temperature":0.7,"pith_summary":"The paper studies local search for minimizing makespan on identical parallel machines, where each move exchanges at most $k$ jobs between two machines. An earlier construction showed that for $k \\ge 3$ this search can need exponentially many improving swaps in the worst case. The paper's claim is that such bad instances are pathological: if processing times are drawn independently from arbitrary densities bounded by $\\varphi$ on $[0,1]$, the expected number of iterations to reach a $k$-swap local optimum is $O(m^2 n^{2k+2} \\log m \\, \\varphi)$. For constant $k$ this is polynomial in $n$ and $m$, so small random noise makes the exponential worst case effectively disappear.","feed_headline":"Noise makes k-swap scheduling search polynomial-time","feed_subtitle":"Perturbed job times make k-swap local search converge in polynomial expected time.","key_machinery":"The argument is carried by the minimum gap $\\delta_{\\min} = \\min |p(A)-p(B)|$ over disjoint job sets $A,B$ with $1 \\le |A|+|B| \\le k$, together with a split of machines into a high-load band $\\gamma_l$ and the rest $\\gamma_s$. Improving swaps are divided into type-1 moves, after which the non-critical machine enters $\\gamma_l$, and type-2 moves, after which it stays in $\\gamma_s$. Type-2 moves are bounded by a potential $\\Phi = \\sum_{i,i'} |L_i - L_{i'}|$ that drops by at least $4\\delta_{\\min}$ each time, and type-1 moves are bounded by charging each consecutive move to a distinct combination of the chosen job sets and the rank $\\ell$ of the least-loaded machine. Smoothed analysis then only needs the probability estimate $P(\\delta_{\\min} \\le \\alpha) \\le 2^{k+1} n^k \\alpha \\varphi$, which converts the deterministic bound into the polynomial expectation.","core_discovery":"Theorem 3.11 is the central discovery. For arbitrary adversary-chosen densities $f_1,\\dots,f_n:[0,1]\\to[0,\\varphi]$ and processing times drawn independently from them, the random variable $T$ counting iterations until a $k$-swap optimal schedule satisfies $\\mathbb{E}[T] = O(m^2 n^{2k+2} \\log m \\, \\varphi)$. The bound holds for every initial schedule and every choice of improving swap, and it follows from a deterministic upper bound of $O(m^2 n^{k+1}/\\delta_{\\min})$ combined with a union-bound estimate showing that the probability of a very small gap $\\delta_{\\min}$ is tiny. The paper therefore proves that the earlier exponential lower bound is a rare worst-case phenomenon rather than a typical behavior.","pith_inferences":["A testable extension is to take the prior exponential $k=3$ construction, add independent uniform noise scaled by a small $\\varepsilon$, and measure iteration counts; the theorem predicts polynomial growth in $n$ for every fixed $\\varepsilon$, in sharp contrast to the noiseless exponential curve.","The proof structure suggests that any local-search neighborhood whose improving moves require a gap of the form $|p(A)-p(B)|$ will inherit a similar smoothed bound, so the machinery may transfer to other subset-exchange neighborhoods beyond $k$-swap.","The linear dependence on $\\varphi$ implies that even weak perturbation, with densities close to but not exactly degenerate, suffices; the only dangerous events are configurations where many subset sums almost coincide, which are exactly the configurations the union bound controls."],"forward_implications":["For any constant $k$, the expected number of local-search iterations is polynomial in the number of jobs and machines, matching the practical observation that convergence is fast.","The exponential worst-case instance for $k \\ge 3$ is not robust: adding even a mild random perturbation to processing times destroys the chain of exponentially many improving swaps.","Because the bound holds for arbitrary improving choices, no tie-breaking or starting schedule can force a long smoothed run, so the polynomial bound is a property of the neighborhood and the noise model rather than of a particular implementation.","The dependence on the perturbation parameter $\\varphi$ is only linear, so the adversary must concentrate densities extremely close to degenerate configurations to approach the exponential worst case.","Type-2 moves contribute at most $O(m n/\\delta_{\\min})$ globally, so most iterations in a long run must be type-1 moves governed by the monotonicity of low machine loads."],"supporting_citations":[{"why":"Introduces smoothed analysis as the framework that connects poor worst-case behavior with good practical performance.","marker":"[36]"},{"why":"Defines the one-step model with adversary-chosen densities bounded by $\\varphi$, which is the exact perturbation model used in Theorem 3.11.","marker":"[6]"},{"why":"The same authors' earlier paper defines the $k$-swap neighborhood and proves the exponential worst-case lower bound for $k\\ge3$ that this smoothed result is designed to contrast.","marker":"[31]"}],"fun_headline_variants":["Smoothed k-swap scheduling runs in expected poly-time","Adversarial noise makes k-swap search polynomial-time","k-swap local search tamed by smoothed analysis","Exponential k-swap rare under perturbed job times","Smoothed analysis gives poly bound for k-swap scheduling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The deterministic bound depends on a counting step that charges each consecutive type-1 swap to a distinct combination of the swapped job sets and the rank of the least-loaded machine; if two different swaps could be charged to the same combination, the bound would break, and the smoothed theorem would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Smoothed k-swap scheduling runs in expected poly-time","Adversarial noise makes k-swap search polynomial-time","k-swap local search tamed by smoothed analysis","Exponential k-swap rare under perturbed job times","Smoothed analysis gives poly bound for k-swap scheduling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000185,"raw_usage":{"total_tokens":1344,"prompt_tokens":988,"completion_tokens":356,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":288}},"tokens_in":604,"tokens_out":356,"duration_ms":4503,"temperature":1.0,"reasoning_tokens":288,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:23:25.667547+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a sequence of consecutive type-1 swaps in which the same pair of job sets is swapped while the least-loaded machine has the same rank more than once, with no type-2 swap in between. Lemma 3.2 says such a repetition is impossible; finding one would invalidate Corollary 3.3 and collapse the deterministic $O(m^2 n^{k+1}/\\delta_{\\min})$ bound and its smoothed consequence.","supporting_citations":[{"cited_title":"Spielman and S.H","cited_arxiv_id":null,"evidence_quote":"Introduces smoothed analysis as the framework that connects poor worst-case behavior with good practical performance."},{"cited_title":"Beier and B","cited_arxiv_id":null,"evidence_quote":"Defines the one-step model with adversary-chosen densities bounded by $\\varphi$, which is the exact perturbation model used in Theorem 3.11."},{"cited_title":"A k-swap Local Search for Makespan Scheduling","cited_arxiv_id":"2401.05956","evidence_quote":"The same authors' earlier paper defines the $k$-swap neighborhood and proves the exponential worst-case lower bound for $k\\ge3$ that this smoothed result is designed to contrast."}],"review_version":1}