I came across this problem wherein there are a number of houses on a 2-D grid (their coordinates are given) and we essentially have to find which house can be used as a meeting point so that the distance traveled by everyone minimizes. Let us assume that a distance along the x or y-axis takes 1 unit and a distance to the diagonal neighbors takes (say) 1.2 units. 

I cannot really think of a good optimization algorithm for this. 

P.S: Not a homework problem. And I am only looking for an algorithm (not code) and if possible, its proof.

P.S #2: I am not looking for the Exhaustive solution. Believe it or not, that did strike me :)