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

V.G. Deineko, G.J. Woeginger

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    56 Citaten (Scopus)
    1 Downloads (Pure)

    Samenvatting

    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.
    Originele taal-2Engels
    Pagina's (van-tot)519-542
    TijdschriftMathematical Programming
    Volume87
    Nummer van het tijdschrift3
    DOI's
    StatusGepubliceerd - 2000

    Vingerafdruk Duik in de onderzoeksthema's van 'A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit