Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.