Pith. sign in

REVIEW 2 major objections 6 minor 36 references

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling

T0 review · 2 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Under random perturbation of processing times, k-swap local search reaches a local optimum in polynomially many expected iterations whenever k is constant.

desk verdict Solid smoothed analysis of k-swap local search for makespan scheduling; main theorem holds, with fixable presentation issues. read the letter →

arxiv 2411.17245 v1 pith:V2QYRL73 submitted 2024-11-26 cs.DS

Lars Rohwedder , Ashkan Safari , Tjark Vredeveld This is my paper · ORCID
classification cs.DS MSC 68W4090B35
keywords smoothedanalysislocalsearchk-swapneighborhoodmakespanschedulingidenticalparallelmachinesiterativeimprovementP||Cmax
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [Theorem 3.11, proof (final displayed equation)] 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.
  2. [Corollary 3.3 and Lemma 3.2] 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.
minor comments (6)
  1. [Lemma 3.10] 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.
  2. [Theorem 3.11 proof] 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.
  3. [Lemma 3.2] The proof writes 'i′ ∈ γℓ(t + 1)' where γℓ is not defined; this should be γl.
  4. [Lemma 3.2] 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.
  5. [Theorem 3.11 proof] 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.
  6. [Section 3, definition of ℓmin-load machine] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the proof is self-contained from the definitions and the only self-citation is motivational context, not a load-bearing input.

full rationale

The main smoothed bound (Theorem 3.11) is obtained by a standard tail-sum over a deterministic iteration bound, Corollary 3.9. That deterministic bound follows from Lemma 3.2 for type-1 swaps, Lemma 3.7 for the type-2 potential drop, and Observation 3.4 bounding the initial potential; all of these are proved from the paper's own definitions of δmin, k-swap, γl/γs, and Φ = Σ|Li−Li′|. Lemma 3.10 bounds P(δmin ≤ α) directly from the density bound φ and a union bound over O((2n)^k) pairs of disjoint job sets; this is an analytic bound on the input distribution, not a fitted parameter renamed as a prediction, and not an imported theorem. The only self-citation is reference [31], used in the abstract and introduction to state the exponential worst-case lower bound and a prior two-machine result as motivation; it does not appear in any proof step needed for Theorem 3.11. The skeptic concern about Corollary 3.3 concerns whether the charging of type-1 swaps to tuples (A,B) is fully explicit; even if that were a proof gap, it would be a correctness defect, not circularity, because it does not reduce the conclusion to an assumption or to a self-citation. There is no self-definitional identification, no fitted-input-called-prediction step, and no uniqueness or ansatz imported through self-citation. The central claim therefore has independent mathematical content; score 1 reflects only the presence of minor motivational self-citation, which is not load-bearing.

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

The proof introduces no free parameters fitted to data and no new postulated entities. It relies only on the standard smoothed analysis model, standard probability bounds, and the local search improvement rule as defined.

assumptions (4)
  • domain assumption Processing times are drawn independently from densities bounded by φ on [0,1].
    One-step smoothed model (Section 3); the theorem's statement is conditional on this model.
  • standard math The density of p(A)-p(B) is at most φ for any disjoint A,B with 1≤|A|+|B|≤k.
    Invoked in Lemma 3.10; follows from convolution of the densities of the individual job times, each bounded by φ, although the paper only sketches this via deferred decisions.
  • domain assumption An improving k-swap requires a critical machine i, a non-critical machine i', and sets A,B with 0 < p(A)-p(B) < Li-Li'.
    Definition of the improvement rule in Section 2; this is the local search rule under analysis.
  • standard math No schedule is visited twice during a run, so T ≤ m^n.
    Each improving step strictly decreases the lexicographic pair (makespan, number of critical machines), used to truncate the tail sum in Theorem 3.11.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling." pith.science (2026). https://pith.science/paper/V2QYRL73

@misc{pith2026241117245,
  author       = {Pith},
  title        = {Pith review of: Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V2QYRL73}},
  note         = {Machine review of arXiv:2411.17245}
}
abstract

Local search is a widely used technique for tackling challenging optimization problems, offering simplicity and strong empirical performance across various problem domains. In this paper, we address the problem of scheduling a set of jobs on identical parallel machines with the objective of makespan minimization, by considering a local search neighborhood, called $k$-swap. A $k$-swap neighbor is obtained by interchanging the machine allocations of at most $k$ jobs scheduled on two machines. While local search algorithms often perform well in practice, they can exhibit poor worst-case performance. In our previous study, we showed that for $k \geq 3$, there exists an instance where the number of iterations required to converge to a local optimum is exponential in the number of jobs. Motivated by this discrepancy between theoretical worst-case bound and practical performance, we apply smoothed analysis to the $k$-swap local search. Smoothed analysis has emerged as a powerful framework for analyzing the behavior of algorithms, aiming to bridge the gap between poor worst-case and good empirical performance. In this paper, we show that the smoothed number of iterations required to find a local optimum with respect to the $k$-swap neighborhood is bounded by $O(m^2 \cdot n^{2k+2} \cdot \log m \cdot \phi)$, where $n$ and $m$ are the numbers of jobs and machines, respectively, and $\phi \geq 1$ is the perturbation parameter. The bound on the smoothed number of iterations demonstrates that the proposed lower bound reflects a pessimistic scenario which is rare in practice.

Figures

Figures reproduced from arXiv: 2411.17245 by the authors.

Figure 1
Figure 1. Jump (left diagram) and swap (right diagram) operators. further improvement can be achieved in the neighborhood, indicating that the current solution has reached a local optimum. In this paper, we consider one of the most fundamental scheduling problems, in which we are given a set of n jobs with positive processing times pj(j = 1, 2, ..., n). Each of these jobs needs to be processed on one of m identical machines w… view at source ↗
Figure 2
Figure 2. k-swap operator. model of the smoothed analysis, known as the one-step model, introduced by Beier and V ¨ocking [6], an adversary specifies probability density functions upper-bounded by φ ≥ 1 for all the numbers that need to be perturbed. Then, all the numbers are drawn independently according to their respective density function. In this setting, the smaller φ, the less powerful the adversary, i.e., the analysis i… view at source ↗
Figure 3
Figure 3. (a) Type-1 of improving k-swap. After swapping A with B, i ′ moves to γl. (b) Type-2 of improving k-swap. After swapping A with B, i ′ stays in γs. Note that in both of the cases, machine i does not necessarily move to γs after the swap. 3. Smoothed Analysis In this section, we provide a smoothed analysis of the number of iterations required to converge to a k-swap optimal solution. To this end, we employ the one-st… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [31]

    A k-swap Local Search for Makespan Scheduling

    L. Rohwedder, A. Safari, and T. Vredeveld. A k-swap loca l search for makespan scheduling. arXiv preprint arXiv:2401.05956, 2024

    work page Pith review arXiv 2024

  2. [1]

    Aarts and J.K

    E.H.L. Aarts and J.K. Lenstra. Local search in combinatorial optimization . Princeton University Press, 2003

    work page 2003

  3. [2]

    Ahuja, J.B

    R.K. Ahuja, J.B. Orlin, and D. Sharma. Multi-exchange ne ighborhood structures for the capacitated minimum spanning tree problem. Mathematical Programming, 91(1):71–97, 2001

    work page 2001

  4. [3]

    Arthur and S

    D. Arthur and S. V assilvitskii. Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. In 47th Annual IEEE Symposium on F oundations of Computer Science (FOCS), pages 153–164, 2006

    work page 2006

  5. [4]

    Banderier, R

    C. Banderier, R. Beier, and K. Mehlhorn. Smoothed analys is of three combinatorial problems. In International Symposium on Mathematical F oundations of Computer Science, pages 198–207. Springer, 2003

    work page 2003

  6. [5]

    Becchetti, S

    L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Sch¨ afer, and T. Vredeveld. Average-case and smoothed competitive analysis of the multilevel feedback algorithm . Mathematics of Operations Research , 31(1):85–108, 2006

    work page 2006

  7. [6]

    Beier and B

    R. Beier and B. V¨ ocking. Random knapsack in expected pol ynomial time. In Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC) , pages 232–241, 2003

    work page 2003

  8. [7]

    Bl¨ aser, B

    M. Bl¨ aser, B. Manthey, and B.V .R. Rao. Smoothed analysis of partitioning algorithms for euclidean functionals. Algorithmica, 66:397–418, 2013

    work page 2013

Show all 36 references
  1. [8]

    Blum and J

    A. Blum and J. Dunagan. Smoothed analysis of the perceptr on algorithm for linear programming. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete alg orithms, pages 905–914, 2002

    2002

  2. [9]

    Boros, K

    E. Boros, K. Elbassioni, M. Fouz, V . Gurvich, K. Makino, a nd B. Manthey. Stochastic mean payoff games: Smoothed analysis and approximation schemes. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 147–158. Springer, 2011

    2011

  3. [10]

    Brucker, J

    P . Brucker, J. Hurink, and F. Werner. Improving local se arch heuristics for some scheduling problems. part II. Discrete Applied Mathematics, 72(1-2):47–69, 1997

    1997

  4. [11]

    Brueggemann, J.L

    T. Brueggemann, J.L. Hurink, T. Vredeveld, and G.J. Woe ginger. Exponential size neighborhoods for makespan minimization scheduling. Naval Research Logistics, 58(8):795–803, 2011

    2011

  5. [12]

    X. Chen, X. Deng, and S.H. Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM, 56(3):1–57, 2009

    2009

  6. [13]

    G.A. Croes. A method for solving traveling-salesman pr oblems. Operations research, 6(6):791–812, 1958

    1958

  7. [14]

    Damerow, B

    V . Damerow, B. Manthey, F.M.A.D. Heide, H. R¨ acke, C. Scheideler, C. Sohler, and T. Tantau. Smoothed analysis of left-to-right maxima with applications. ACM Transactions on Algorithms, 8(3):1–28, 2012

    2012

  8. [15]

    Englert, H

    M. Englert, H. R¨ oglin, and B. V¨ ocking. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68(1):190–264, 2014

    2014

  9. [16]

    Finn and E

    G. Finn and E. Horowitz. A linear time approximation alg orithm for multiprocessor scheduling. BIT Numerical Mathematics, 19(3):312–320, 1979

    1979

  10. [17]

    M.M. Flood. The traveling-salesman problem. Operations research, 4(1):61–75, 1956

    1956

  11. [18]

    M. Fouz, M. Kufleitner, B. Manthey, and N. Zeini Jahromi. On smoothed analysis of quicksort and hoare’s find. Algorithmica, 62(3-4):879–905, 2012

    2012

  12. [19]

    Frangioni, E

    A. Frangioni, E. Necciari, and M.Grazia. Scutella. A mu lti-exchange neighborhood for minimum makespan parallel machine scheduling problems. Journal of Combinatorial Optimization , 8(2):195–220, 2004. 8 Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling

    2004

  13. [20]

    R.L. Graham. Bounds for certain multiprocessing anoma lies. Bell system technical journal , 45(9):1563–1581, 1966

    1966

  14. [21]

    R.L. Graham. Bounds on multiprocessing timing anomali es. SIAM journal on Applied Mathematics , 17(2):416– 429, 1969

    1969

  15. [22]

    Graham, E.L

    R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinn ooy Kan. Optimization and approximation in determin- istic sequencing and scheduling: a survey. In Annals of discrete mathematics, volume 5, pages 287–326. Elsevier, 1979

    1979

  16. [23]

    Hochbaum and D.B

    D.S. Hochbaum and D.B. Shmoys. Using dual approximatio n algorithms for scheduling problems theoretical and practical results. Journal of the ACM , 34(1):144–162, 1987

    1987

  17. [24]

    Hurkens and T

    C.A.J. Hurkens and T. Vredeveld. Local search for multi processor scheduling: how many moves does it take to a local optimum? Operations Research Letters, 31(2):137–141, 2003

    2003

  18. [25]

    Johnson and M.R

    D.S. Johnson and M.R. Garey. Computers and intractability: A guide to the theory of NP-co mpleteness. WH Freeman, 1979

    1979

  19. [26]

    B. Manthey. Smoothed analysis of local search algorith ms. In W orkshop on Algorithms and Data Structures , pages 518–527. Springer, 2015

    2015

  20. [27]

    Manthey and R

    B. Manthey and R. Reischuk. Smoothed analysis of binary search trees. Theoretical Computer Science , 378(3):292–315, 2007

    2007

  21. [28]

    Manthey and J

    B. Manthey and J. van Rhijn. Improved smoothed analysis of 2-opt for the euclidean TSP. arXiv preprint arXiv:2211.16908, 2022

    2022 arXiv

  22. [29]

    D. Marx. Parameterized complexity and approximation a lgorithms. The Computer Journal, 51(1):60–78, 2008

    2008

  23. [30]

    Michiels, E.H.L

    W . Michiels, E.H.L. Aarts, and J. Korst. Theoretical aspects of local search , volume 13. Springer, 2007

    2007

  24. [32]

    Sankar, D.A

    A. Sankar, D.A. Spielman, and S.H. Teng. Smoothed analy sis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications , 28(2):446–476, 2006

    2006

  25. [33]

    Sch¨ afer and N

    G. Sch¨ afer and N. Sivadasan. Topology matters: Smoothed competitiveness of metrical task systems. Theoretical Computer Science, 341(1-3):216–246, 2005

    2005

  26. [34]

    Schuurman and T

    P . Schuurman and T. Vredeveld. Performance guarantees of local search for multiprocessor scheduling. IN- FORMS Journal on Computing , 19(1):52–63, 2007

    2007

  27. [35]

    Spielman and S.H

    D.A. Spielman and S.H. Teng. Smoothed analysis of termi nation of linear programming algorithms. Mathemati- cal Programming, 97:375–404, 2003

    2003

  28. [36]

    Spielman and S.H

    D.A. Spielman and S.H. Teng. Smoothed analysis of algor ithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385–463, 2004. 9

    2004

Pith tools

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