A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

V.G. Deineko, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    56 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP.
    Original languageEnglish
    Pages (from-to)519-542
    JournalMathematical Programming
    Volume87
    Issue number3
    DOIs
    Publication statusPublished - 2000

    Fingerprint Dive into the research topics of 'A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem'. Together they form a unique fingerprint.

    Cite this