From: "J.R. Gutierrez" <jrgutier@...>
Date: 2010-09-17T06:09:08+09:00
Subject: NP-Hard Geolocatoin Problem

I am trying to create a program that maximizes the distances of
addresses in Y amount of groups, essentially trying to decrease the
chance that you are in the same group as your neighbors.

Here is an example n it's simplest form. Say there are four people, two
living in Los Angeles, one in New York, and one in Chicago that needed
to be divided into two groups. The logical grouping would be {LA, CHI}
and {LA, NY).

Now a more complex example. Imagine 1000 people, 400 of which reside in
the Southern California area, 200 in the NY area, 100 in the Northern
California area, and the rest peppered in the area within the country.
We need to separate them into 16 groups. Ideally, depending on
distances, there would be 400/16 SoCal residents in a group.

I've been trying hard to find out how to characterize this problem in a
way that can be calculated with a computer using Ruby. The only way I
can get an optimal answer by brute-forcing the distance between X people
(X! calculations) and then doing something with that information to
divide them into evenly distributed groups. I've also tried to think of
this as reverse gravity problem, where the closer two people live to
each other, the more they repel each other when deciding groups.

So my question is, is there any kind of similar problem where I can
borrow some kind of algorithm to compute an optimal answer? Or can
anyone at least point me in the right direction?
-- 
Posted via http://www.ruby-forum.com/.