All-exp property conjectures for local search
There exists a constant and infinitely many Traveling Salesman Problem instances with cities, together with an initial Hamiltonian cycle , such that every sequence of strictly improving -opt moves starting from and ending at a -opt local optimum has length at least .
References
- Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment — arXiv — Sophia Heimann, Hung P. Hoang, Stefan Hougardy
Source: arXiv
Progress summary
A new unrefereed paper claims exponential-length improvement behavior in several local-search settings, but related cases remain open.
The conjectures ask when every improving local-search sequence must be exponentially long, rather than merely allowing one unlucky exponential sequence. The latest paper claims to settle three specified neighborhoods, including -opt TSP and two constraint-assignment cases.
Known results
- For -MCA with flips, the all-exp property is proved for every ; each constructed sequence has length .
- Every improving sequence for -MCA has length .
- The and MCA cases have the weaker is-exp property, while all-exp remains open.
- In TSP, -opt, -opt, and constant are covered, while earlier work left -opt open.
October 2026 claimed advance
The paper claims infinitely many instances forcing every improving sequence to be exponential in three stated neighborhoods, with polynomial behavior after parameter reduction, thereby closing the advertised gaps. The claim is unverified; no independent assessment or identified error was found.
Current status (as of October 2026): the reported paper claims progress on -opt TSP and two assignment settings, but the broader family, including MCA cases and , remains open and the new claims are unverified.
Solutions 0
No solutions have been posted yet.