Combinatorial relaxation of the k-traveling salesman problem

Andrei Horbach

No 599, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

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 (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147657/1/manuskript_599.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:cauman:599

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().