Let $P$ be an $m \times m$ antisymmetric matrix of the form: $$ \begin{bmatrix} 0 & p_{1,2} & ... & p_{1,m} \\ -p_{1,2} & 0 & ... & p_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ -p_{1,m} & -p_{2,m} & \dots & 0 \\ \end{bmatrix}$$

with $p_{i,j} \in [+1,-1]$, how can I find a set $I^*$ of matrix rows that maximizes the following function: $$ f(I) = \left( \sum_{i \in I} \sum_{j=0}^{m} p_{i,j} \right)^2 + \sum_{i \in I} \sum_{j \in M \setminus I} \left(1-p_{i,j}^2\right) $$

Obviously, an exhaustive search requires $2^m$ steps but I was wondering if it is possible to do better. I was thinking about dynamic programming but was unable to come up with a solution.

Let $I_0^*=\{\ \}$, i.e. the empty set, be the solution for all sets of size zero. For sets containing only one row it is easy to find $I_1^*=\max_k f(I_0^* \cup \{\ k\})$ as one can just compute the function value for each row $k$ separately.

If I do: $$I_h^* = \max_{k \notin I_{h-1}} f\left( I_{h-1}^* \cup \{\ k\} \right)$$ I end up with a greedy solution which, from testing, does not appear to exhibit the best solution. I am not sure if the problem lacks optimal substructure. So is there any better solution?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.