Arbeitspapier
Combinatorial relaxation of the k-traveling salesman problem
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.
- Language
-
Englisch
- Bibliographic citation
-
Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 599
- Classification
-
Management
- Subject
-
k-traveling salesman problem
k-TSP
matching
2-matching
1-tree
Rundreiseproblem
Theorie
Matching
- Event
-
Geistige Schöpfung
- (who)
-
Horbach, Andrei
- Event
-
Veröffentlichung
- (who)
-
Universität Kiel, Institut für Betriebswirtschaftslehre
ZBW – Leibniz Information Centre for Economics
- (where)
-
Kiel
- (when)
-
2005
- Handle
- Last update
-
10.03.2025, 11:42 AM CET
Data provider
This object is provided by:
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
Object type
- Arbeitspapier
Associated
- Horbach, Andrei
- Universität Kiel, Institut für Betriebswirtschaftslehre
- ZBW – Leibniz Information Centre for Economics
Time of origin
- 2005
Other Objects (12)
The traveling salesman problem
Das Traveling-Salesman-Problem, [1]
Approximation Algorithms for Traveling Salesman Problems
Curve reconstruction and the traveling salesman problem
On The Recoverable Robust Traveling Salesman Problem
Das Traveling Salesman Problem unter disjunktiven Zusatzrestriktionen
Approximation Algorithms for the Traveling Salesman Problem
Das Traveling-Salesman-Problem : Anwendungen und heuristische Nutzung von Voronoi-Delaunay-Strukturen zur Lösung euklidischer, zweidimensionaler Traveling-Salesman-Probleme
A Polyhedral Study of Quadratic Traveling Salesman Problems
Effiziente Heuristiken für das probabilistische Traveling salesman Problem
Provably good solutions for the traveling salesman problem
Das Konvergenzverhalten der Evolutionsstrategie für Traveling-Salesman-Probleme
The traveling salesman problem
Das Traveling-Salesman-Problem, [1]
Approximation Algorithms for Traveling Salesman Problems
Curve reconstruction and the traveling salesman problem
On The Recoverable Robust Traveling Salesman Problem
Das Traveling Salesman Problem unter disjunktiven Zusatzrestriktionen
Approximation Algorithms for the Traveling Salesman Problem
Das Traveling-Salesman-Problem : Anwendungen und heuristische Nutzung von Voronoi-Delaunay-Strukturen zur Lösung euklidischer, zweidimensionaler Traveling-Salesman-Probleme
A Polyhedral Study of Quadratic Traveling Salesman Problems
Effiziente Heuristiken für das probabilistische Traveling salesman Problem
Provably good solutions for the traveling salesman problem
Das Konvergenzverhalten der Evolutionsstrategie für Traveling-Salesman-Probleme
The traveling salesman problem
Das Traveling-Salesman-Problem, [1]
Approximation Algorithms for Traveling Salesman Problems
Curve reconstruction and the traveling salesman problem
On The Recoverable Robust Traveling Salesman Problem
Das Traveling Salesman Problem unter disjunktiven Zusatzrestriktionen
Approximation Algorithms for the Traveling Salesman Problem
Das Traveling-Salesman-Problem : Anwendungen und heuristische Nutzung von Voronoi-Delaunay-Strukturen zur Lösung euklidischer, zweidimensionaler Traveling-Salesman-Probleme
A Polyhedral Study of Quadratic Traveling Salesman Problems
Effiziente Heuristiken für das probabilistische Traveling salesman Problem
Provably good solutions for the traveling salesman problem