Pith. sign in

REVIEW 3 major objections 5 minor 37 references

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The 3-opt and 4-opt algorithms for the traveling salesman problem can take exponentially many improving steps before reaching a local optimum, no matter which pivot rule is used.

desk verdict Resolves k=3 and k=4 for TSP k-opt with a solid gadget construction; the 2.5-opt branch rests on a proof sketch that needs rigorous completion. read the letter →

arxiv 2507.12304 v1 pith:L4DI6PTF submitted 2025-07-16 cs.DS cs.DM

Sophia Heimann , Hung P. Hoang , Stefan Hougardy This is my paper
classification cs.DScs.DM MSC 68Q2590C27
keywords k-optalgorithmall-exppropertytravelingsalesmanproblem2.5-optlocalsearchMax-Cutpivotruleexponentiallowerbound
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

This paper answers a long-standing open question: how many iterations can the widely used 3-opt and 4-opt heuristics for the traveling salesman problem need, even when the algorithm chooses optimally among improving moves? The answer is exponential: the authors prove both have the 'all-exp property', meaning there are infinitely many instances and starting tours on which every improving sequence to a local optimum has exponential length, so no pivot rule can help. The proof builds TSP instances that faithfully simulate a hard Max-Cut local-search instance, so each improving flip of a Max-Cut vertex becomes an improving 3- or 4-swap in the tour. The same construction, with different gadgets, gives the same exponential lower bound for the practical 2.5-opt algorithm, and all results carry over to metric TSP. With the previously known $k \geq 5$ case, this settles the optimal-pivot-rule iteration count for every $k \geq 3$, leaving only 2-opt open.

What carries the argument

The argument is carried by a gadget reduction from Max-Cut/Flip to TSP/$k$-opt whose bridge is a class of 'standard tours'. A vertex gadget (a stick gadget for $k=3$, a buoy gadget for $k=4$, an XOR gadget for $k \geq 5$) has two sides corresponding to the two sides of the Max-Cut, and a path gadget is attached along each path of a fixed $2$-path $2$-cover of the Max-Cut graph; by Lemma 13 each path gadget has exactly one subtour per sign vector, and its edge weights are set so that the tour weight is the negative of the cut value (Lemma 21). Cuts and standard tours are then in bijection, improving flips are exactly improving $k$-swaps (Lemma 22), and the transition graphs of the two local-search problems are isomorphic as long as only standard tours occur (Lemma 23). The load-bearing mechanism that keeps the simulation inside this subspace is Lemma 24: a swap that turns a standard tour into a non-standard tour must touch at least $g/2$ edges, where $g$ is the girth of the Max-Cut graph; the proof builds an auxiliary graph whose edges are the inconsistent gadget sides and shows its cycles wrap around cycles of the Max-Cut graph. Setting $p=15$ gives girth 18, so a 4-swap (at most 8 edges) cannot escape, and the exponential Max-Cut flip sequence is faithfully reproduced. The 2.5-opt variant replaces vertex gadgets with node gadgets and path gadgets with star gadgets, including a star-4 gadget engineered for specific vertices of a further-modified Max-Cut instance, and extracts the one-edge saving from deliberately 'irregular' engagement of the node gadgets.

What would settle it

Run the $k$-opt algorithm from the constructed initial tour for small instance sizes and check whether every improving sequence stays standard and matches the predicted Max-Cut flip sequence. For $k=3,4$, the theorem predicts that the first improving step leaving a standard tour would need at least $g/2 = 9$ edge exchanges, so any improving 4-swap from a standard tour to a non-standard tour would falsify Lemma 24; for 2.5-opt, any improving 2.5-swap producing a non-standard tour from a standard one would falsify Lemma 41.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1, is that the 3-opt and 4-opt algorithms have the all-exp property: there are infinitely many pairs (instance, initial tour) such that every improving $k$-swap sequence from the initial tour to a local optimum has length exponential in the number of vertices, regardless of the pivot rule. The proof reduces from Max-Cut/Flip on graphs of maximum degree four, starting from the Michel-Scott family of Max-Cut instances as modified in the authors' earlier work, which has a unique improving flip sequence of exponential length. Each Max-Cut vertex is replaced by a vertex gadget whose engaged side records which side of the cut the vertex lies on, and each path in a fixed $2$-path $2$-cover is replaced by a path gadget whose weights make the tour weight equal the negative of the cut value; the resulting 'standard tours' stand in one-to-one correspondence with cuts, and one flip corresponds to one $k$-swap (Lemmas 21–23). Since any escape from the standard-tour subspace requires at least $g/2$ edge exchanges for a Max-Cut graph of girth $g$ (Lemma 24), choosing girth 18 ensures no 4-swap can leave the subspace, so every improving sequence follows the exponential Max-Cut flip sequence. An analogous but more intricate gadget construction, exploiting newly introduced 'irregular' behavior, proves the same exponential lower bound for 2.5-opt (Theorem 3), and adding a constant to all edge weights transfers all results to metric TSP.

Load-bearing premise

The load-bearing premise is that every improving $k$-swap sequence from the initial tour stays inside the 'standard tours' that encode cuts of the Max-Cut instance; this rests on the cycle-counting bound of Lemma 24, and if some gadget configuration allowed a cheaper escape from the standard subspace, the exponential Max-Cut flip sequence would no longer be simulated.

Editorial extensions

If this is right

  • For $k=3$ and $k=4$, no pivot rule, steepest descent included, can guarantee even a sub-exponential worst-case number of iterations: the hard instances defeat every choice rule.
  • Together with the earlier $k \geq 5$ result, the iteration complexity of $k$-opt under an optimal pivot rule is now resolved for every $k \geq 3$, leaving only 2-opt open.
  • Because every TSP instance can be made metric by adding a constant to all edge weights, the same exponential lower bounds hold for metric TSP, so the triangle inequality does not restore polynomial behavior.
  • The 2.5-opt algorithm, a practical compromise that outperforms 2-opt without the full cost of 3-opt, also has the all-exp property under every pivot rule.
  • For $k \geq 5$, the new reduction preserves the entire transition graph between the Max-Cut instance and the TSP instance, giving a simpler proof of the previously known lower bound.

Reading between the lines

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

  • The hard instances constructed here use edge weights that grow exponentially in the instance size (powers of $8^n$ and perturbations of order $2^{-n}$), so the results leave open whether polynomially weighted or Euclidean instances can also force exponential $k$-opt runs; smoothed and average-case analysis remains the natural explanation of the heuristics' practical speed.
  • The paper's own diagnosis of why $k=2$ resists the approach — the need to simulate flips of high-degree vertices with 2-swaps while keeping the tour connected — suggests the obstruction is global connectivity of the tour rather than the local gadget simulation, and it does not rule out a polynomial worst-case bound for 2-opt under an optimal pivot rule.
  • The 'irregular' engagement trick that saves one exchanged edge in the 2.5-opt construction looks transferable: other local-search problems whose neighborhood size falls just short of a reduction threshold might be proved hard by allowing solutions to interact with gadgets in deliberately non-canonical ways.
  • The single exceptional state in the 2.5-opt construction — the star-4 subtour (n), whose successor in the cyclic state sequence requires a plain 2-swap instead of a 2- or 2.5-change — marks exactly where the reduction is tightest; checking whether that exception is removable is a concrete way to probe the construction's slack.
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

3 major / 5 minor

Summary. This paper proves that the 3-opt and 4-opt heuristics for the traveling salesman problem have the all-exp property: there are infinitely many TSP instances and initial tours such that every improving k-swap sequence to a local optimum has exponential length, for every pivot rule. The proof reduces Max-Cut/Flip instances H_{n,p} with girth 18 and a fixed 2-path 2-cover to TSP instances using stick gadgets (k=3), buoy gadgets (k=4), and path gadgets; a girth/auxiliary-cycle argument (Lemma 24) is used to show that no improving 3- or 4-swap can leave the subspace of standard tours, so the one-to-one correspondence in Lemma 23 transfers the exponential Max-Cut flip sequence to an exponential TSP swap sequence. The paper also establishes an analogous exponential lower bound for the 2.5-opt algorithm using a further modified Michel-Scott construction H'_{n,p}, irregular node gadgets, and star gadgets including a star-4 gadget; the key Lemma 29 asserts that every maximal improving flip sequence of H'_{n,p} has exponential length and projects to a recursive sequence L'_n, but its proof is only sketched. A final section gives an alternative construction for k >= 5.

Significance. If correct, the paper resolves two of the three remaining open cases in the exponential-time complexity of k-opt under an optimal pivot rule, leaving only k=2 open; together with the authors' earlier ICALP 2024 result this completes the picture for all k >= 3. The k=3,4 architecture is modular and the girth barrier in Lemma 24 is a clean and convincing idea, and the 2.5-opt construction introduces genuinely new gadget behavior (irregular node gadgets and star-4 gadgets) that is likely to be useful beyond this paper. The paper does not ship machine-checked proofs, and the 2.5-opt branch currently rests on a proof sketch for a load-bearing lemma, which lowers confidence in that branch even though the 3-opt/4-opt theorem appears structurally sound.

major comments (3)
  1. [Section 7.1, Lemma 29] The proof of Lemma 29 is not a complete proof. After the inductive step the text says "we now go through at least the sequence L'_{n-1} (and potentially some other vertices of the form u_{i,3,2}, u_{i,5,4}, u_{i,7,6})" and later "Continuing with a similar argument as before, we then obtain the lemma statement." This leaves two possibilities open that would invalidate Theorem 3: (i) an improving flip of one of the "free" vertices u_{i,3,2}, u_{i,5,4}, u_{i,7,6} could occur at a time when it is not forced and could change the happiness status of v_{i,3}, v_{i,5}, or v_{i,7}, creating a shortcut; (ii) a vertex of F'_{n,p} other than u_{n,3,2} could become unhappy during the traversal of L'_{n-1}, allowing an extra flip that changes the projected subsequence. Since Observation 30, Claim 43, and the final Theorem 3 all depend on the exact projection property and on every maximal improving flip sequence having exponential length, Lemma 29 needs a complete, step-by-step proof rather than a sketch with a citation to [29,15].
  2. [Section 8.2, Claim 43] In the exceptional star-4 case for v in {v_{i,3}, v_{i,5}, v_{i,7}}, the proof asserts "we can change this subtour to subtour (b) by a 2-swap" without demonstrating the two removed and two added edges. This transition is load-bearing because it is the one place where the argument does not directly simulate the improving flip; if the stated 2-swap does not exist, the construction of the improving swap from τ_r fails. The proof should give an explicit edge-level verification of the transition from subtour (n) to subtour (b), especially since the caption of Figure 17 says it shows only "some (but not all)" pairs of subtours.
  3. [Section 5.4, Lemma 24] The statement that a non-standard tour must contain at least one path gadget with a non-standard subtour is asserted in one sentence and deserves more care, because for the stick and buoy gadgets some non-standard subtours share the same underlying edge set as standard subtours. Since a tour in this paper is an edge set, the argument should explicitly rule out the possibility that τ' differs from τ only by such a relabeling of a vertex-gadget subtour; otherwise the lower bound "at least g/2 edges" could fail in that degenerate case. I believe this is fixable, but it should be stated precisely.
minor comments (5)
  1. [Figure 14 and Observation 30] The cyclic order of Π is ambiguous in the text: the successor relation used in the proof of Claim 43 appears to be the reverse of the vertical listing in Figure 14. Please add arrows or otherwise specify the cyclic orientation explicitly.
  2. [Lemma 24] The lemma states a lower bound of g/2 edges; when g is odd this is not an integer. In the application g=18, so the issue is harmless, but the statement should use ceil(g/2) or explicitly restrict to even g.
  3. [Abstract and Introduction] The phrase "resolves this question" should be read as "establishes exponential lower bounds" rather than a complete resolution including upper bounds; consider rewording to avoid implying that the number of iterations is now characterized exactly.
  4. [Section 7.1, Observation 30 paragraph] There is a small typo: "for j ∈ [4], a_i = 1 if and only if u_i is in the 1-set" should read "a_j = 1 if and only if u_j is in the 1-set."
  5. [Section 5.1, Lemma 17] Lemma 17 is imported verbatim from the authors' own ICALP 2024 paper and is a black box for the exponential lower bound in Theorem 1. This is acceptable, but the paper should state the exact version being used, including the uniqueness of the maximal improving flip sequence and any restrictions on the weight function, so that the reader does not have to consult [15] to verify the statement.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new k=3,4 and 2.5-opt all-exp results are genuine reductions from an external Max-Cut/Flip lower bound; the lone self-citation (Lemma 17) is independent support, and the proof-sketch gap in Lemma 29 is a rigor concern, not a circular step.

full rationale

The derivation chain is a reduction, not a self-justifying loop. Theorem 1 starts from the modified Michel-Scott Max-Cut instance of Lemma 17 (cited to the authors' ICALP 2024 paper), independently proves in Lemma 18 that H_{n,p} has girth p+3 and is 2-path 2-coverable, and then builds TSP gadgets that establish, in Lemmas 21-23, a one-to-one correspondence between improving Max-Cut flip sequences and improving k-swap sequences that stay within standard tours. Lemma 24 independently shows that leaving the standard-tour subspace requires at least g/2 edge exchanges; with girth 18 this exceeds the 8 edges a 4-swap can touch, so every improving k-swap sequence from the standard initial tour remains in the subspace. The exponential TSP lower bound is therefore derived, not assumed: it transfers a separate exponential Max-Cut lower bound via an explicit gadget construction. The 2.5-opt branch similarly reduces to Lemma 29, an in-paper Max-Cut statement whose proof is given only as an inductive sketch ('Continuing with a similar argument as before, we then obtain the lemma statement'). This is a proof-completeness risk for Theorem 3, as the skeptic notes, but it is not a case of the conclusion being equivalent to the input: the missing details concern the internal behavior of the Max-Cut flip sequence, not the TSP reduction. The only self-citation is Lemma 17 from the authors' own ICALP paper; it is load-bearing, but its assumptions concern Max-Cut/Flip, not TSP, it does not include the target result, and it is externally checkable in the cited prior work, so under the stated rules it counts as independent support and does not raise the circularity score. No fitted parameter is relabeled as a prediction, and no uniqueness theorem is invoked to forbid alternative constructions; the uniqueness of the Max-Cut flip sequence is a used structural property, not a forced conclusion of the TSP argument. Finding: no significant circularity (score 0).

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

The central claim rests on an external Max-Cut lower bound, a prior exponential Max-Cut construction from the authors' own ICALP paper [15], and a set of large explicitly constructed gadget graphs. The freely chosen parameters are the girth parameter p, two small epsilon constants used to order improving moves, and the exponential weight ladder in the adversarial Max-Cut instances. The gadgets are explicit mathematical constructions rather than unexplained postulated entities.

free parameters (4)
  • p = 15 for k=3,4; at least 7 for k=2.5
    Odd integer controlling the girth of the Max-Cut graph H_{n,p}, which has girth p+3; p=15 gives girth 18 so escaping standard tours requires at least 9 edge changes, more than the 8 edges of a 4-swap.
  • epsilon = 2^-n
    Small weight decrement in the further modified Michel-Scott weights; it forces the prescribed flip order in Lemma 29 and is chosen by hand.
  • tilde_epsilon = 2^-2n
    Small constant in the star-4 gadget weights; n*tilde_epsilon is below any improving flip gain, which is used in Corollary 42.
  • exponential weight ladder = weights of order 8^n, 8^(n+1)
    Adversarial instance weights in the modified Michel-Scott construction make each vertex's improving status depend on the intended neighbor; these are construction parameters, not fitted to data.
assumptions (4)
  • standard math Max-Cut/Flip has the all-exp property on graphs of maximum degree four.
    External hardness source from Monien-Tscheuschner and Michel-Scott; it is the starting point of the reduction in Sections 3 through 5.
  • domain assumption Modified Michel-Scott instances H_{n,p} have a weight function and an initial cut whose unique maximal improving flip sequence has exponential length (Lemma 17, from [15]).
    The paper reproduces the construction but imports the exponential-length statement from the authors' ICALP 2024 paper [15]; this is load-bearing for Theorems 1 and 3.
  • ad hoc to paper Lemma 29: every maximal improving flip sequence of H'_{n,p} from gamma'_{n,p} has exponential length and contains the sequence L'_n.
    The proof is given only as a sketch with the comment 'similar to the proof of the exponential running time in [29,15]'; it is central to the 2.5-opt theorem and should be expanded before full acceptance.
  • standard math Adding a sufficiently large constant to all TSP edge weights preserves the k-opt transition graph and makes an instance metric.
    Used in the abstract and Section 1.1 to extend all-exp results from general TSP to metric TSP.
invented entities (4)
  • Stick gadget
    purpose: Vertex gadget for k=3; switching between odd and even subtours costs 0 edges.
    Constructed in Definition 8; its properties are proven in the paper and there is no empirical prediction.
  • Buoy gadget
    purpose: Vertex gadget for k=4; switching between odd and even subtours costs 2 edges.
    Constructed in Definition 10; subtours are enumerated in Figure 8 and properties are proven internally.
  • Path-1, path-2, and path-3 gadgets
    purpose: Encapsulate the contribution of Max-Cut edge weights to the tour weight through agreeing and disagreeing weights.
    Defined in Section 4.3; uniqueness and weights of standard subtours are proven in Lemma 13.
  • Star gadgets (star-1 through star-4) and irregular node gadgets
    purpose: Model induced stars in H for the 2.5-opt construction; irregular behavior lets a flip be simulated with fewer exchanged edges.
    Defined in Section 7; properties are asserted in Lemmas 32 through 41 and Figures 15 through 17, with no external falsifiable handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem." pith.science (2026). https://pith.science/paper/L4DI6PTF

@misc{pith2026250712304,
  author       = {Pith},
  title        = {Pith review of: A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L4DI6PTF}},
  note         = {Machine review of arXiv:2507.12304}
}
abstract

The $k$-opt algorithm is one of the simplest and most widely used heuristics for solving the traveling salesman problem. Starting from an arbitrary tour, the $k$-opt algorithm improves the current tour in each iteration by exchanging up to $k$ edges. The algorithm continues until no further improvement of this kind is possible. For a long time, it remained an open question how many iterations the $k$-opt algorithm might require for small values of $k$, assuming the use of an optimal pivot rule. In this paper, we resolve this question for the cases $k = 3$ and $k = 4$ by proving that in both these cases an exponential number of iterations may be needed even if an optimal pivot rule is used. Combined with a recent result from Heimann, Hoang, and Hougardy (ICALP 2024), this provides a complete answer for all $k \geq 3$ regarding the number of iterations the $k$-opt algorithm may require under an optimal pivot rule. In addition we establish an analogous exponential lower bound for the 2.5-opt algorithm, a variant that generalizes 2-opt and is a restricted version of 3-opt. All our results hold for both the general and the metric traveling salesman problem.

Figures

Figures reproduced from arXiv: 2507.12304 by the authors.

Figure 1
Figure 1. All three local changes are valid for 3-opt, but only (a) is valid for 2-opt. 2.5- [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The two vertex gadgets used in our construction: (a) stick gadget for [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. (a) Path-1 gadget, (b) path-2 gadget, and (c) path-3 gadget. Edge weights [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: Visualization of our construction of a TSP instance from a Max-Cut instance. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: A very simple example of the constructed TSP instance for the Max-Cut [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: If we simply let two vertices of each side of a path-3 gadget coincide, then there [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Irregular behavior (left) and regular behavior (right). The gray boxes represent [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: (a) Stick gadget. (b) Buoy gadget. (c) Subtour in a buoy gadget that is an [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Path gadgets. Subtour edges are in red. Unless specified, edges have weight [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: The full construction of the TSP instance as represented in Fig. [PITH_FULL_IMAGE:figures/full_fig_p016_10.png]
Figure 11
Figure 11. Figure 11: Hn,p with a 2-path 2-cover. The paths of length two are either solid thick blue paths or solid thin purple paths. The dashed edges indicate paths of length one. The two 0-paths (v ′ 2 ) and (vn,8) are not shown in this figure. Note that the relative positions of vn−1,…
Figure 12
Figure 12. Figure 12: The XOR gadget of order four (a) and its two standard subtours ((b) and (c)). [PITH_FULL_IMAGE:figures/full_fig_p023_12.png]
Figure 13
Figure 13. Figure 13: Further modified Michel-Scott construction. The colors of the vertices indicate [PITH_FULL_IMAGE:figures/full_fig_p025_13.png]
Figure 14
Figure 14. Figure 14: The cyclic sequence Π For the remaining of this section, we define H := H′ n,p and w := wn,p for some p ≥ 3 that we will specify later. 7.2 Node gadgets To avoid confusion with the behavior of the vertex gadgets in the previous construction, we use the term node gadge…
Figure 15
Figure 15. Figure 15: Star gadgets. Edges not in a subtour are dashed. Unless specified, edges have [PITH_FULL_IMAGE:figures/full_fig_p029_15.png]
Figure 16
Figure 16. Figure 16: Star-4 gadget and the 14 standard subtours. Edges not in a subtour are dashed. [PITH_FULL_IMAGE:figures/full_fig_p030_16.png]
Figure 17
Figure 17. Figure 17: All the standard subtours of a star-4 gadget, with edges describing some (but [PITH_FULL_IMAGE:figures/full_fig_p031_17.png]
Figure 18
Figure 18. Figure 18: Assignments of node and star gadgets. Black nodes represent regular node [PITH_FULL_IMAGE:figures/full_fig_p031_18.png]
Figure 19
Figure 19. Figure 19: The cycle of H˜ as described in the proof of Lemma 39. Solid edges and dash edges are edges of types (i) and (ii), respectively. 34 [PITH_FULL_IMAGE:figures/full_fig_p034_19.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

37 extracted references · 35 canonical work pages

  1. [1]

    Avis and V

    D. Avis and V. Chv´ atal. Notes on Bland’s pivoting rule. In M. L. Balinski and A. J. Hoffman, editors, Polyhedral Combinatorics: Dedicated to the memory of D.R. Fulkerson, number 8 in Mathematical Programming Study, pages 24–34. North- Holland Publishing Company, 1978

    work page 1978

  2. [2]

    Fast algorithms for geometric traveling salesman problems.ORSA Journal on Computing , 4(4):387–411, 1992

    Jon Jouis Bentley. Fast algorithms for geometric traveling salesman problems.ORSA Journal on Computing , 4(4):387–411, 1992

    work page 1992

  3. [3]

    Exponential lower bounds for many pivot rules for the sim- plex method

    Alexander E Black. Exponential lower bounds for many pivot rules for the sim- plex method. In Nicole Megow and Amitabh Basu, editors, Proceedings of the 26th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2025, Baltimore, MD, USA, June 11–13, 2025 , pages 86–99. Springer, 2025

    work page 2025

  4. [4]

    Brodowsky, Stefan Hougardy, and Xianghui Zhong

    Ulrich A. Brodowsky, Stefan Hougardy, and Xianghui Zhong. The approximation ratio of the k-opt heuristic for the Euclidean traveling salesman problem. SIAM Journal on Computing , 52(4):841–864, 2023

    work page 2023

  5. [5]

    New results on the oldk-opt algo- rithm for the traveling salesman problem

    Barun Chandra, Howard Karloff, and Craig Tovey. New results on the oldk-opt algo- rithm for the traveling salesman problem. SIAM Journal on Computing , 28(6):1998– 2029, 1999

    work page 1998

  6. [6]

    George B. Dantzig. Origins of the simplex method. In Stephen G. Nash, editor, A history of scientific computing , pages 141–151. Association for Computing Machin- ery, 1990

    work page 1990

  7. [7]

    Yann Disser, Oliver Friedmann, and Alexander V. Hopp. An exponential lower bound for Zadeh’s pivot rule. Mathematical Programming, 199:865–936, 2023

    work page 2023

  8. [8]

    Smoothed analysis of the 2- opt algorithm for the general TSP

    Matthias Englert, Heiko R¨ oglin, and Berthold V¨ ocking. Smoothed analysis of the 2- opt algorithm for the general TSP. ACM Trans. Algorithms, 13(1), September 2016

    work page 2016

Show all 37 references
  1. [9]

    Worst case and probabilistic analysis of the 2-opt algorithm for the TSP

    Matthias Englert, Heiko R¨ oglin, and Berthold V¨ ocking. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68:190–264, 2014

    2014

  2. [10]

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

    1956

  3. [11]

    On the Smoothed Complexity of Combinatorial Local Search

    Yiannis Giannakopoulos, Alexander Grosz, and Themistoklis Melissourgos. On the Smoothed Complexity of Combinatorial Local Search. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium 39 on Automata, Languages, and Programmi...

    2024

  4. [12]

    On the smoothed complexity of combinatorial local search

    Yiannis Giannakopoulos, Alexander Grosz, and Themistoklis Melissourgos. On the smoothed complexity of combinatorial local search. arXiv:2211.07547 [cs.CC], 2025

    2025

  5. [13]

    Worst case behavior of the steepest edge simplex method

    Donald Goldfarb and William Y Sit. Worst case behavior of the steepest edge simplex method. Discrete Applied Mathematics , 1(4):277–285, 1979

    1979

  6. [14]

    A. Haken. Connectionist networks that need exponential time to stabilize. Technical report, University of Toronto, Department of Computer Science, 1989

    1989

  7. [15]

    Hoang, and Stefan Hougardy

    Sophia Heimann, Hung P. Hoang, and Stefan Hougardy. The k-opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5. In 51st International Colloquium on Automata, Languages, and Programming, volume 297 of LIPIcs. Leibniz Int. Proc. Inform. , pages...

    2024

  8. [16]

    Hoang and Stefan Hougardy

    Hung P. Hoang and Stefan Hougardy. On the PLS-completeness of TSP/k-opt. Tech- nical Report No: 231275, Research Institute for Discrete Mathematics, University of Bonn, 2023

    2023

  9. [17]

    The approximation ratio of the 2-opt heuristic for the metric traveling salesman problem

    Stefan Hougardy, Fabian Zaiser, and Xianghui Zhong. The approximation ratio of the 2-opt heuristic for the metric traveling salesman problem. Operations Research Letters, 48(4):401–404, 2020

    2020

  10. [18]

    R. G. Jeroslow. The simplex algorithm with the pivot rule of maximizing criterion improvement. Discrete Mathematics, 4:367–377, 1973

    1973

  11. [19]

    Johnson and Lyle A

    David S. Johnson and Lyle A. McGeoch. The traveling salesman problem: a case study. In Emile Aarts and Jan Karel Lenstra, editors, Local Search in Combinatorial Optimization, pages 215–310. Wiley, 1997

    1997

  12. [20]

    Johnson and Lyle A

    David S. Johnson and Lyle A. McGeoch. Experimental analysis of heuristics for the STSP. In Gregory Gutin and Abraham P. Punnen, editors, The traveling salesman problem and its variations , pages 369–443. Kluwer Academic Publishers, 2002

    2002

  13. [21]

    Johnson, Christos H

    David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences , 37(1):79–100, 1988

    1988

  14. [22]

    Kleitman

    Gil Kalai and Daniel J. Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin of the American Mathematical Society , 26(2):315–316, 1992

    1992

  15. [23]

    Mount, Nathan S

    Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Computational Geometry, 28:89–112, 2004

    2004

  16. [24]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, 1972) , pages 85–103, 1972. 40

    1972

  17. [25]

    Victor Klee and George J Minty. How good is the simplex algorithm? In Oved Sisha, editor, Inequalities — III, Proceedings of the Third Symposium on Inequalities Held at The University of California, Los Angeles, September 1–9, 1969 , pages 159–175. Academic Press, 1972

    1969

  18. [26]

    Structure in locally optimal solutions

    Mark W Krentel. Structure in locally optimal solutions. In 30th Annual Symposium on Foundations of Computer Science, pages 216–221. IEEE Computer Society, 1989

    1989

  19. [27]

    Computer solutions of the traveling salesman problem

    Shen Lin. Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 44(10):2245–2269, 1965

    1965

  20. [28]

    Improved smoothed analysis of 2-opt for the euclidean TSP

    Bodo Manthey and Jesse van Rhijn. Improved smoothed analysis of 2-opt for the euclidean TSP. Algorithmica, 2025

    2025

  21. [29]

    Superpolynomial smoothed complexity of 3-flip in local max-cut

    Lukas Michel and Alex Scott. Superpolynomial smoothed complexity of 3-flip in local max-cut. arXiv:2310.19594v1 [cs.DS] , 2023

    2023 arXiv

  22. [30]

    On the power of nodes of degree four in the local max-cut problem

    Burkhard Monien and Tobias Tscheuschner. On the power of nodes of degree four in the local max-cut problem. In Tiziana Calamoneri and Josep Diaz, editors, Algo- rithms and Complexity , volume 6078 of Lecture Notes in Comput. Sci. , pages 264–

  23. [31]

    Papadimitriou

    Christos H. Papadimitriou. The adjacency relation on the traveling salesman poly- tope is NP-complete. Mathematical Programming, 14(1):312–324, 1978

    1978

  24. [32]

    Papadimitriou, Alejandro A

    Christos H. Papadimitriou, Alejandro A. Sch¨ affer, and Mihalis Yannakakis. On the complexity of local search. In Proceedings of the twenty-second annual ACM symposium on Theory of Computing (STOC’90) , pages 438–445, 1990

    1990

  25. [33]

    Integer linear programs and local search for max-cut

    Svatopluk Poljak. Integer linear programs and local search for max-cut. SIAM J. Comput., 24(4):822–839, 1995

    1995

  26. [34]

    Sch¨ affer and Mihalis Yannakakis

    Alejandro A. Sch¨ affer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing , 20(1):56–87, 1991

    1991

  27. [35]

    Computational complexity

    Mihalis Yannakakis. Computational complexity. In Emile Aarts and Jan Karel Lenstra, editors, Local Search in Combinatorial Optimization, pages 19–55. Princeton University Press, Princeton and Oxford, second edition, 2003

    2003

  28. [36]

    On the approximation ratio of the k-opt and lin-kernighan algo- rithm for metric and graph tsp

    Xianghui Zhong. On the approximation ratio of the k-opt and lin-kernighan algo- rithm for metric and graph tsp. In 28th Annual European Symposium on Algorithms (ESA 2020) , pages 83–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2020. 41

    2020

  29. [275]

    Springer Berlin Heidelberg, 2010

    2010

Pith tools

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