patternMinor
What kind of NP problem would this be
Viewed 0 times
thisproblemwhatwouldkind
Problem
I have N by N symmetrical matrix with each side having the same items.
In reality this would be much larger (100 x 100)
I am trying to find a subset of a fixed size in this matrix with the highest score. For example the selection ABC would be:
It is kinda like traveling salesman problem, but with the final distance only determined by the final selection.
A B C D
A 0
B 4 0
C 8 3 0
D 3 1 8 0In reality this would be much larger (100 x 100)
I am trying to find a subset of a fixed size in this matrix with the highest score. For example the selection ABC would be:
AB = 4;
AC = 8;
BC = 3;
Total 15It is kinda like traveling salesman problem, but with the final distance only determined by the final selection.
Solution
You can reduce clique (or independent set) to your problem, so it is NP-hard. Just take the adjacency matrix as your matrix, use the same parameter $k$ (the size of the clique), and declare that there is a clique in the graph if the maximum score is $\binom{k}{2}$.
Context
StackExchange Computer Science Q#14886, answer score: 2
Revisions (0)
No revisions yet.