The travelling salesman problem (TSP) is well known (https://en.wikipedia.org/wiki/Travelling_salesman_problem). Let us look at the Euclidean TSP throughout this question.

There is a generalization of the travelling salesman problem where several salesman occur. All of them start at the same city and have to return there. For each salesman a round trip has to be found and every city (except from the starting city, which we consider as fixed an given) has to be visited by exactly one salesman. The objective is to minimize the longest tour.

I am interested in results of the following form:

Let $n \in \mathbb N$ be the number of cities.

1.Denote the values of the optimal solutions with $OPT_{TSP}$ and $OPT_{mTSP}$ respectively. What is the maximum value for $K=K_n\geq 1$ such that there is an instance where $OPT_{TSP} \geq K\cdot OPT_{mTSP}$?

2.How does $K$ behave asymptotically for $n \rightarrow \infty$?

I would be grateful for references about this or related topics. Thanks!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.