Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
Abstract
We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for (3,2,2)- and (2,3,2)-Maximum Constraint Assignment with the flip neighborhood. The all-exp property states that infinitely many instances have an initial solution from which every sequence of improving moves to a local optimum, and hence every run of local search, has exponential length. For the Traveling Salesman Problem, the all-exp property was previously known for every k-opt neighborhood with k ≥ 3, so our result for $2$-opt completes the picture for all k-kopt neighborhoods. In (p,q,r)-Maximum Constraint Assignment, each constraint involves at most p variables, each variable occurs in at most q constraints, and each domain has size r. Decreasing any of the parameters of (3,2,2) or (2,3,2) yields a problem in which every sequence of improving flips has polynomial length, so both Maximum Constraint Assignment results are tight. All three results settle long-standing open problems. Our proofs build on a common construction idea, which reveals a close connection between the local-search dynamics of the three problems.
Related
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- Traveling Salesman Problem on Graphs with Proportional Independent Set
- On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem
- Collaborative Attention Ant Colony Optimization for Large-Scale Traveling Salesman Problems
- Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand
BibTeX
@misc{heimann2026closing,
title = {{Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment}},
author = {Sophia Heimann and Hung P. Hoang and Stefan Hougardy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31513},
eprint = {2610.31513},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31513},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
AU - Sophia Heimann
AU - Hung P. Hoang
AU - Stefan Hougardy
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31513
UR - https://arxiv.org/abs/2610.31513
AB - We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for (3,2,2)- and (2,3,2)-Maximum Constraint Assignment with the flip neighborhood. The all-exp property states that infinitely many instances have an initial solution from which every sequence of improving moves to a local optimum, and hence every run of local search, has exponential length. For the Traveling Salesman Problem, the all-exp property was previously known for every k-opt neighborhood with k ≥ 3, so our result for $2$-opt completes the picture for all k-kopt neighborhoods. In (p,q,r)-Maximum Constraint Assignment, each constraint involves at most p variables, each variable occurs in at most q constraints, and each domain has size r. Decreasing any of the parameters of (3,2,2) or (2,3,2) yields a problem in which every sequence of improving flips has polynomial length, so both Maximum Constraint Assignment results are tight. All three results settle long-standing open problems. Our proofs build on a common construction idea, which reveals a close connection between the local-search dynamics of the three problems.
ER -