# Does anyone know the name of the following problem?

At a given day a number of $N$ salesmen (from the same company) are randomly scattered in a landscape with $M$ cities. At the next day as many cities as possible should have a salesman visiting, no two salesmen going to the same city. To what city $c_j$ should each salesman $s_i$ go to, in order to minimize the total distance travelled for all salesmen.

Note that if $M$ is less than $N$ some salesmen should stay on place and not go anywhere. We also assume that each salesmen can reach each city in the given time.

I would also be thankful for any pointer to algorithms solving the problem!

-
I don't understand "as many cities as possible": you can always visit N cities, if there's no constraint on the total distance covered by all salesmen (or by a single salesman). –  gd1 Jan 15 '13 at 16:11
Thanks, @Rahul, for the link (and answer!). I "jumped the gun"! –  amWhy Jan 15 '13 at 16:14
I just meant that if there are more cities than salesmen, all cities would not have a salesman visiting. –  Simon Jan 15 '13 at 16:24
Thank you Rahul! –  Simon Jan 15 '13 at 16:30

## 1 Answer

In a comment, Rahul Narain suggests that this problem can be thought of as an example of the assignment problem. Normally one thinks of assigning agents (salesmen) to tasks, and each assignment has a certain cost. Here the tasks are cities, and the costs are determined by the distances between the salesmen's current locations and their potential target cities.

-