[Algorithm] Split Into Maximal Groups

[Nestharus]

Asked this awhile ago

http://stackoverflow.com/questions/...can-i-split-them-into-the-largest-clusters-po


Still unsolved


Any takers?

 

[Yixx]

Tried to formalise this problem. After some thinking and googling I found this:
http://en.wikipedia.org/wiki/Exact_cover_problem
http://en.wikipedia.org/wiki/Knuth's_Algorithm_X

If you can find a set of all sets that fit the description you gave, at most k points and all within some circle of radius r, then the exact cover problem solves your problem.

However, this would mean having to calculate a subset of the Power set of the points, which can be quite costly, certainly as n and k increase, and on top of that the Exact Cover Problem is NP-Complete. I'm not really sure what that means as somehow people in this university tend not to elaborate on that, but from what I read I think there is no efficient deterministic polynomial time algorithm.

I guess you would have to settle with an exponential or maybe even worse solution.. but more research would have to be done to be certain. Maybe a different interpretation of the problem can lead to a different but efficient solution....

 

[Kanadaj]

I wonder what this is needed for

 

[Dr Super Good]

I think this might be one of these cases where an approximation will have to be good enough. Kind of like the traveling salesman problem. As long as the clusters are mostly full all the time any kind of approximation will suffice.

 

[Nestharus]

The thing is, if they are full, something happens, and if they aren't, nothing happens.

So 2 being mostly full and a third being full = only 1 thing happening, vs a possible 2 things happenin >.<.


There is no mostly, it's either full or it isn't.

 

[Dr Super Good]

Yes so you are after designing an algorithm that gets as many possible full. If that is the maximum number of full ones (perfect solution) should not mater as long as the result is very close to the perfect solution.

I imagine you will need some kind of iterative algorithm that generates a rough approximation of the solution and then iteratively refines it (maybe even with randomness for a chance of better results).