The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

Author:
  • CPChristos H. Papadimitriou
    Christos H. Papadimitriou

Abstract
It is shown that finding a local optimum solution with respect to the Lin–Kernighan heuristic for the traveling salesman problem is PLS-complete, and thus as hard as any local search problem.

This publication has 8 references indexed in Scilit: