Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements

Question

Suppose $A$ is an $n \times n$ matrix, and $k \ge 1$ is an integer. We want to find $k$ distinct indices from $\{1, 2, \ldots, n\}$, denoted as $i_1, \ldots, i_k$, such that

$\sum_{p, q = 1}^k A_{i_p, i_q}$

is maximized. In words, we seek $k$ rows and the corresponding $k$ columns, such that the intersected $k^2$ elements of $A$ have the largest sum.

This problem can be formulated as a quadratic assignment problem, which is NP-hard and admits no polynomial time algorithm with constant approximation bound. I'm just wondering if for this specific problem (as a special case of quadratic assignment), there exists a poly-time algorithm with constant approximation bound. Thank you.

Answer 1

There is an easy reduction from the well-known NP-complete problem MAX-CLIQUE to your problem. Recall that in MAX-CLIQUE we are given a graph $G$ and an integer $k$, and have to decide whether $G$ contains a $k$-clique. We can recast this as an instance of your problem as follows: the matrix $A$ is the adjacency matrix of your graph, and the goal is to determine whether there is a choice of indices for which the sum equals $\binom{k}{2}$.