-

 

 

 




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

 

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