Given a real m*n matrix A (m rows, n columns), a real positive number b. Each entry in A can be positive or negative.
Find a subset of columns to maximize the number of rows whose sum of entries in those selected columns is at least b.
The equivalent mathematical formulation: $$ \max_{x\in\{0,1\}^n} \sum_{i=1}^{m} I(A_{i.}x-b) $$ where
- $I(x) = 1 \text{ if } x\geq0, 0$ otherwise.
- $A_{i.}$ is the row vector of the i-th column of A
- $x$ is a binary column vector of size n.
What I have tried so far:
- When m=1, the problem is equivalent to the optimization version of the subset sum problem, assuming entries of A are non-negative numbers (Even if the assumption is violated, my solution is to add the absolute value of the most negative value in that row to all the entries and b) The reference to the optimization of subset sum is here (https://courses.cs.washington.edu/courses/csep521/05sp/lectures/sss.pdf)
Current I am stuck when $m\geq2$. I have looked at generalized assignment problem (https://en.wikipedia.org/wiki/Generalized_assignment_problem), weighted bipartite graphs (https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_weighted_bipartite_graphs). However, I cannot reduce my problem to any of the above two.
Please kindly advise.
Did you manage to solve this problem? I am trying to solve exactly the same problem... I think for m = 1, it is not subset sum sine subset sum is looking for a subset whose sum equals precisely b, while not at least b. If it is at least b, as in your problem, the best way is to just pick all the non-negative columns and sum them up -- this the largest sum you could get.
It is not clear how to solve this problem for large m.