Instance: Given a matrix of size $m\times n$ of positive real numbers, $m$ real numbers $L_i$ for all $i\in\{1,\cdots,m\}$ and an integer $k$ less or equal than $n$.

Question: Is there a subset of columns, $S\subset\{1,\cdots,n\}$ of cardinality $k$ (i.e., $|S|\leqslant k$), such that the sum of row $i$ is greater or equal than $L_i$ for all $i\in\{1,\cdots,m\}$. That is, is there a subset $S\subset\{1,\cdots,n\}$ such that $$\sum_{\substack{j\in S\\|S|\leqslant k}}a_{ij}\geqslant L_i.$$

How to solve this problem?

I am particularly interested in the case where $L_i$ are all equal for all $i\in\{1,\cdots,m\}$.

I think that it is related to the $K$th heaviest subset problem which is NP-hard. As defined in this book, the $K$th heaviest subset problem is:

  • Instance: Given integers $c_1$, $\cdots$, $c_n$, $K$ and $L$.

  • Question: Are there distinct subsets $S_1$, $\cdots$, $S_K\subseteq\{1,\cdots,n\}$ such that

$$\sum_{j\in S_i}c_j\geqslant L\quad\quad\text{ for } i=1,\cdots, K?$$

  • $\begingroup$ Well then: what have you tried and where did you get stuck? Have you confirmed that the problem is NP-hard? If so, what kind of sacrifice are you willing to make? $\endgroup$ – Raphael Jan 26 '16 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.