Algorithm for finding subset of permutations with maximum value

Hello,
Can anyone help with suggestions for implementation of an efficient algorithm for the following issue:
Given a list of permutations with a score for each permutation, we need to find a subset of permutations with the highest summed score, given the condition that any one of permutation in the subset will not intersect or be contained with another permutation in the subset.
For example, given the following list of permutations, marked as |Index: start, end, score|, permutation A cannot be in the same subset with permutation B, since they intersect with each other. Permutation C cannot be in the same subset with permutation F, since permutation F is contained within permutation C.

A: 43 70 27
B: 45 74 26
C: 3 28 24
D: 65 99 45
E: 20 39 26
F: 10 18 20
G: 78 97 23

I guess the challenge is to implelent this in O(NlogN) rather than the naïve implemention of O(N2)
Thanks in advance!

Tom.

This is essentially a "knapsack" problem (see wikipedia), and is loosely in the same type of problems as the travelling salesman.
or in short, no actual algorithm exists for this.

for small datasets you can bruteforce an answer
for large datasets, you can only find a "good" answer within a certain amount of time but you can't guarantee "the best" answer in a reasonable amount of time.
A variety of different methods have been used to find solutions to this with various success and performance. such as ant farms, genetic algorithms, ...

Quote:

---

Originally Posted by OReubens

or in short, no actual algorithm exists for this.

---

Of course there exists an algorithm. This for example,

1. Generate all possible subsets of the N "permutations". There are 2^N such subsets.
2. From all possible subsets select the valid (no conflicting "permutations") subsets.
3. From all valid subsets pick the one(s) with the highest score sum.

This is not a polynominal algorithm (it's something like O(2^N * N * logN)) so it's intractable for big N, still it's a working algorithm.

Quote:

---

Originally Posted by mayeri

I guess the challenge is to implelent this in O(NlogN) rather than the naïve implemention of O(N2)

---

Well if you have an O(N^2) algorithm already you've come quite far. :)

To me it looks like your problem is equivalent to the Weighted Interval Scheduling Problem. To see that you only have to view your "permutations" as weighted time intervals (jobs) with a start time, an end time and a weight (score).

http://pages.cs.wisc.edu/~shuchi/cou...notes/lec3.pdf

According to the article there's an O(N * logN) algorithm available indeed for this problem.