Search:

Yes but how could i know if it is NP complete?
is there a way to verify that?

Yes i read it, what i'm looking for is this:

we have x villages and m hospitals.
we place the hospitals.
every village is distant "L" from it's nearest hospital. (ex:if village is at km 4, and...

I'm not so sure of that, i mean, A and C doesn't directly interact between them, but if i balance B and C, then i have to adjust the position of B and C centers...then i need to rebalance A and B...

I'm not sure that you need to balance it only one time...i mean, if i balance B and C, then i pass to C and D and i find out that they need to be balanced. Now my C and D groups are different then...

S@rK0Y, i had time to read your solution only now, the computation time is intresting, but how many times do you need to balance them? I've not tought deeply about it, but at a guess, every time i...

sorry razzle, the greedy approach you were suggesting is interesting, but the result is not optimum, after that how do you manage to balance everything and get the optiumum solution?

sorry, can you explain better?

sure, in you example is pretty straightforward, but it is possible that you have to move a lot of them, maybe even move an element two or more times, in the end i think that we will end up with the...

Exactly razzle, worst case is n = 2m, and its teta(n*binom(n m))...

sadly i think superbonzo is right, i tried on paper a few examples, and there are situation where dividing into groups with max distance require so many aproximation that it is not worth it...

Thanks, i was thinking something like it but you formalized it better...i'll try it, though i'm not sure how much computation time the "corrections" will require, it could be a lot, tomorrow i'll try...

Ok thanks a lot!

I think i get the point, but i didn't understand everything, sorry but my math notion are not superlative^^

The best optimization i came out with is the bruteforce, which should be...

S@rk0y: I thought of that, but it is not correct...i'll make an example:

|_|_|_|_|__|

the villages are at distance 1 one another, except the last one. I need to put two hospitals. Following...

The point of the problem is to find the fastest algorithm possible, so i don't think teta(N^M) is the best one, not even close

Yes, I thought of that, the problem is that the computation cost is around N^M, which is really bad, i'm sure that there is something better...

Hi everyone, i have a difficult problem to solve, and i need a risolutive algorithm, but i just can't find a solution to it...i'll explain the problem:

I have N villages and M hospitals.
The...