What is this matrix column-selection problem, and how hard is it to approximate?

Question

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.

Answer 1

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.