3
$\begingroup$

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?

$\endgroup$

0

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.