Searching the k-change neighborhood for TSP is W[1]-hard

Searching the k-change neighborhood for TSP is W[1]-hard

0.00 Avg rating—0 Votes
Article ID: iaor20102787
Volume: 36
Issue: 1
Start Page Number: 31
End Page Number: 36
Publication Date: Jan 2008
Journal: Operations Research Letters
Authors:
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.