Find maximal subset with interesting weight function You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th column, then add up all the maximums.
For example, for $n = 4$, $k = 2$ and rows $(1, 4), (2, 3), (3, 2), (4, 1)$ the weight of subset $(1, 4), (2, 3), (3, 2)$ is $\max\{1, 2, 3\} + \max\{4, 3, 2\} = 3 + 4 = 7$.
The question is, having $m \leq n$, find the subset of size $m$ (from given $n$ rows) with maximal weight.
The problem looks trivial when $m \geq k$, but how can one solve it for $m &lt; k$? Looks like dynamic programming on subsets could work for small $k$, isn't it? Are there other ways to do it?
Definitely NP-hard, since it can be used to encode a maximisation form of Vertex Cover in which we ask for the maximum number of edges that can be covered by any subset of $k$ vertices: The input matrix here is just the incidence matrix of the graph, with vertices in the rows and edges in the columns.