A greedy or dynamic algorithm to subset selection

Question

I have a simple algorithmic question. I would be grateful if you could help me.

We have some 2 dimensional points. A positive weight is associated to them (a sample problem is attached). We want to select a subset of them which maximizes the weights and neither of two selected points overlap each other (for example, in the attached file, we cannot select both A and C because they are in the same row, and in the same way we cannot select both A and B, because they are in the same column.) If there is any greedy (or dynamic) approach I can use. I'm aware of non-overlapping interval selection algorithm, but I cannot use it here, because my problem is 2 dimensional.

Any reference or note is appreciated.

Regards

Attachment: A simple sample of the problem:

   
   A (30$) --------  B (10$)
   |
   |
   |
   |
   C (8$)

Answer 1

If you are OK with a good solution, and do not demand the best solution - you can use heuristical algorithms to solve this.

Let S be the set of points, and w(s) - the weightening function.

Create a weight function W:2^S->R (from the subsets of S to real numbers):

W(U) =    - INFINITY                         is the solution is not feasible
          Sigma(w(u)) for each u in U        otherwise

Also create a function next:2^S -> 2^2^S (a function that gets a subset of S, and returns a set of subsets of S)

next(U) = V   you can get V from U by adding/removing one element to/from U

Now, given that data - you can invoke any optimization algorithm in the Artificial Intelligence book, such as Genetic Algorithm or Hill Climbing.

For example, Hill Climbing with random restarts, will be something like that:

1. best<- -INFINITY
2. while there is more time
3. choose a random subset s
4. NEXT <- next(s)
5. if max{ W(v) | for each v in NEXT} < W(s): //s is a local maximum
   5.1. if W(s) > best: best <- W(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max { NEXT }
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

The above algorithm is anytime - meaning it will produce better results if given more time.