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.
- Sprache
-
Englisch
- Erschienen in
-
Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 599
- Klassifikation
-
Management
- Thema
-
k-traveling salesman problem
k-TSP
matching
2-matching
1-tree
Rundreiseproblem
Theorie
Matching
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Horbach, Andrei
- Ereignis
-
Veröffentlichung
- (wer)
-
Universität Kiel, Institut für Betriebswirtschaftslehre
ZBW – Leibniz Information Centre for Economics
- (wo)
-
Kiel
- (wann)
-
2005
- Handle
- Letzte Aktualisierung
-
10.03.2025, 11:42 MEZ
Datenpartner
Dieses Objekt wird bereitgestellt von:
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Arbeitspapier
Beteiligte
- Horbach, Andrei
- Universität Kiel, Institut für Betriebswirtschaftslehre
- ZBW – Leibniz Information Centre for Economics
Entstanden
- 2005
Ähnliche Objekte (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