3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ No. This generalizes Densest k-subgraph. $\endgroup$
    – cangrejo
    Mar 17 '20 at 11:36
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you very much. $\endgroup$
    – user306101
    Mar 17 '20 at 22:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.