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

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.

• No. This generalizes Densest k-subgraph. – cangrejo Mar 17 '20 at 11:36

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}$$.