Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
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 \ge 3$, so our result for $2$-opt completes the picture for all $k$-kopt…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.31513
curl -X POST /api/v1/records/arxiv/2610.31513/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.31513/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'