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.