1
$\begingroup$

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 < k$? Looks like dynamic programming on subsets could work for small $k$, isn't it? Are there other ways to do it?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.