Combinatorial relaxations of the k-traveling salesman problem

Andrei Horbach (horbachbwl.uni-kiel.de)

Abstract: 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: k-traveling salesman problem, k-TSP, matching, 2-matching, 1-tree

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Graphs and Matroids )

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

Download: [Postscript][PDF]

Entry Submitted: 10/14/2005
Entry Accepted: 10/14/2005
Entry Last Modified: 10/14/2005

Modify/Update this entry