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

Documenti analoghi

• The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
  di: Heimann, Sophia, et al.
  Pubblicazione: (2024)
• On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
  di: Heimann, Sophia, et al.
  Pubblicazione: (2026)
• The Bottom-Left Algorithm for the Strip Packing Problem
  di: Hougardy, Stefan, et al.
  Pubblicazione: (2024)
• Extending Exact Integrality Gap Computations for the Metric TSP
  di: Cook, William, et al.
  Pubblicazione: (2026)
• A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
  di: Hougardy, Stefan, et al.
  Pubblicazione: (2025)