Optimization Online


Combinatorial relaxations of the k-traveling salesman problem

Andrei Horbach (horbach***at***bwl.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society