Take the 2-minute tour ×
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.

I remember reading once about the following algorithm:

Consider a lattice grid and $N$ houses situated at grid points, in which live the town elders. They want to choose a lattice point location where they will build the city hall, such that the total distance walked by all $N$ elders is minimized. The algorithm consists of choosing an initial site at random, and then considering an adjacent site. The town elders then vote on whether to switch to the new site, only considering their own walking distances. The process repeats until no better site can be found, then that site clearly minimizes the sum of the walking distances.

Is there a general use for this type of technique (by that I mean the iterated small-shifts and then voting on them)?

share|improve this question
1  
Sounds like a form of hill-climbing. I'm not sure whether there's a specific name for this form. –  Peter Taylor Jan 13 '12 at 10:14
    
To me, it is not clear that this procedure minimizes the sum of the walking distances; a priori, it is possible that $n/2+1$ of people go very short distance, but $n/2-1$ go very long, and switching to another site could very slightly increase the cost for $n/2+1$ of people, but decrease significantly the cost for $n/2-1$ of people. –  sdcvvc Jan 13 '12 at 11:40
    
We only shift the site to adjacent grid points, and we use taxicab distance, so it's all fine. –  Scaramouche Jan 13 '12 at 15:19

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.