A Note on Approximation Algorithms for the Multicriteria \(\Delta\)-TSP

  • The Tree and Christofides heuristic are weil known 1- and \(\frac{1} {2}\)- approximate algorithms for the \(\Delta\)-TSP. In this note their performance for the multicriteria case is described, depending on the norm in \(\mathbb{R}^Q\) in case of \(Q\) criteria.

Export metadata

Additional Services

Search Google Scholar
Author:Matthias Ehrgott, Alexander Feldmann
Series (Serial Number):Preprints (rote Reihe) des Fachbereich Mathematik (266)
Document Type:Report
Language of publication:English
Date of Publication (online):2017/11/06
Year of first Publication:1995
Publishing Institution:Technische Universit├Ąt Kaiserslautern
Date of the Publication (Server):2017/11/06
Page Number:5
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)