pipette
ENEnglish

Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

Preprint

En palabras de los autores

We prove the all-exp property for the Traveling Salesman Problem with the -opt neighborhood, and for - and -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 -opt neighborhood with , so our result for -opt completes the picture for all -kopt neighborhoods. In -Maximum Constraint Assignment, each constraint involves at most variables, each variable occurs in at most constraints, and each domain has size . Decreasing any of the parameters of or 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 36 pages