3
$\begingroup$

I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place it.

The input is a set $A^1,\ldots,A^m \in {\mathbb R}^{n \times n}$ of $n\times n$ real-valued matrices. A feasible solution is a set of columns $S \subseteq \{1,\ldots,n\}$. The value of $S$ is the sum, over all matrices $A^k$, of the maximum sum of a row of $A^k$ when restricted to columns $S$. Formally,

$ val(S) = \sum_{k=1}^m \max_{i=1}^n A^k_i \cdot 1_S,$

where $A^k_i$ denotes the i'th row of matrix $A^k$, $\cdot$ denotes dot product, and $1_S$ denotes the $\{0,1\}$ vector with a 1 in columns corresponding to S. The objective is to find a set of columns $S$ maximizing $val(S)$.

Is this problem well known? What is known about the polynomial-time solvability or approximability of this problem?

Here is what I know. Observe that this problem is trivial when the matrices all have nonnegative entries --- here picking S to be all columns is optimal. The problem is also trivial when the input consists of a single matrix --- simply try all rows and select all positive entries in the row. Therefore, this problem is interesting only when the input consists of many matrices, and the matrices have both positive and negative entries. A (simple though nontrivial) reduction from max-cut shows that this problem is NP-hard, and UGC-hard to (multiplicatively) approximate better than the Goemans-Williamson constant. Beyond that, I don't know much else.

$\endgroup$
  • $\begingroup$ If you can prove that the exact version is NP-hard, then I think that that fact can be used to show that the problem of deciding whether the optimal value is positive or not is NP-complete, hence any multiplicative approximation is NP-hard. $\endgroup$ – Tsuyoshi Ito Feb 8 '13 at 5:03
  • $\begingroup$ Perhaps, though such reductions are usually based on modifying the objective such that to subtract an equal increment from each feasible solution. It is unclear how to do that here. $\endgroup$ – srd Feb 8 '13 at 5:54
  • $\begingroup$ I agree. I thought that that reduction was easy here, but the reduction I was thinking of turned out to be incorrect. $\endgroup$ – Tsuyoshi Ito Feb 8 '13 at 6:20
4
$\begingroup$

After more thought, I found a simple approximation-preserving reduction from independent set, showing that this problem is hard to approximate better than $n^{0.5}$. Here it is.

Consider a graph $G=(V,E)$ with n vertices. Construct the following matrices, with columns indexing the vertices.

  • For each vertex $v$, construct a matrix with the top row containing a 1 in column v, and a 0 elsewhere. All remaining rows are filled with $-\infty$.
  • For each edge $e=(u,v) \in E$, construct a matrix with the first row with $-\infty$ at $u$ and $0$ elsewhere, and the second row with $-\infty$ at $v$ and $0$ elsewhere. All remaining rows are filled with $-\infty$.

The matrices corresponding to edges penalize choosing two adjacent vertices in the graph by $-\infty$, essentially enforcing that the selected set of columns is an independent set of vertices. The matrices corresponding to vertices add one to the objective value for each column selected (i.e. for each vertex included in the independent set). Consequently, $val(S)$ is $-\infty$ for all non-independent sets S, and |S| for all independent sets S.

This shows that the maximum of val(S) is as hard to approximate as the maximum cardinality of an independent set, as needed.

$\endgroup$

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.