Combinatorial relaxation of the k-traveling salesman problem - Andrei Horbach (Universität Kiel, Institut für Betriebswirtschaftslehre; ZBW – Leibniz Information Centre for Economics, 2005)
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.
Keywords: 650; k-traveling salesman problem; k-TSP; matching; 2-matching; 1-tree; Rundreiseproblem; Theorie; Matching