Skip to main content
Became Hot Network Question
edited tags
Link
xskxzr
  • 7.6k
  • 5
  • 23
  • 47
Source Link

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.