Searching the k-change neighborhood for TSP is W[1]-hard |
| |
| Authors: | Dániel Marx |
| |
| Institution: | Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany |
| |
| Abstract: | We show that searching the k-change neighborhood is W1]-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). |
| |
| Keywords: | Traveling Salesperson Problem W[1]-hardness Parameterized complexity Local search |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
