Combinatorial relaxations of the k-traveling salesman problem

  • Andrei Horbach
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , , , Short URL: https://optimization-online.org/?p=9023

    The k-traveling salesman problem, or k-TSP is: given a graph with edge weights and an integer k, find a simple cycle of minimum weight visiting exactly k nodes. To obtain lower bounds for the traveling salesman problem the 2-matching relaxation and the 1-tree relaxation can be used. We generalize these two relaxations for the k-TSP.

    Citation

    599, Institut of Business Administration, University Kiel, October 2005

    Article

    Download

    View Combinatorial relaxations of the k-traveling salesman problem