Thumbnail - Request a copy

Complexity and approximation for Traveling Salesman Problems with profits

Angelelli, Enrico; Bazgan, Cristina; Speranza, Maria Grazia; Tuza, Zsolt (2014), Complexity and approximation for Traveling Salesman Problems with profits, Theoretical Computer Science, 531, p. 54-65. 10.1016/j.tcs.2014.02.046

Type
Article accepté pour publication ou publié
Date
2014
Journal name
Theoretical Computer Science
Volume
531
Publisher
Elsevier
Pages
54-65
Publication identifier
Metadata
Show full item record
Author(s)
Angelelli, Enrico
University of Brescia
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Speranza, Maria Grazia
University of Brescia
Tuza, Zsolt
Department of Computer Science and Systems Technology [Veszprem]
Abstract (EN)
In TSP with profits we have to find an optimal tour and a set of customers satisfying a specific constraint. In this paper we analyze three different variants of TSP with profits that are NP-hard in general. We study their computational complexity on special structures of the underlying graph, both in the case with and without service times to the customers. We present polynomial algorithms for the polynomially solvable cases and fully polynomial time approximation schemes (FPTAS) for some NP-hard cases.
Subjects / Keywords
TSP; Routing problem with profit; Computational complexity; Approximation algorithm; Path; Tree; Cycle
JEL
C44 - Operations Research; Statistical Decision Theory