Searching the k-change neighborhood for a traveling salesperson problem (TSP) is W[1]-hard

Searching the k-change neighborhood for a traveling salesperson problem (TSP) is W[1]-hard

0.00 Avg rating—0 Votes
Article ID: iaor2009699
Country: Netherlands
Volume: 36
Issue: 1
Start Page Number: 31
End Page Number: 36
Publication Date: Jan 2008
Journal: Operations Research Letters
Authors:
Keywords: heuristics, heuristics: local search
Abstract:

We show that searching the k-change neighborhood is W[1]-hard for metric TSP, which means that finding the best tour in the k-change neighborhood essentially requires complete search (modulo some complexity-theoretic assumptions).

Reviews

Required fields are marked *. Your email address will not be published.