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.
Complexity and approximation for Traveling Salesman Problems with profits
ANGELELLI, Enrico;SPERANZA, Maria Grazia;
2014-01-01
Abstract
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
