2

For an academic project, we are trying to solve the following problem.

Given $k$ and a matrix $M$ with $r$ rows and $c$ columns, we want to find a set $K$ of $k$ rows such that

$$\sum_{i=1}^c \min_{j \in K} M[j][i])$$

is minimal.

It can be seen that a (probably not so tight) upper bound for the complexity is $r \choose k$$ \cdot c$; it is my conjecture that the problem is NP-complete.

I have implemented some quick and dirty Branch and Bound algorithm, although it doesn't really scale to the numbers that I would like them to.. I would like to prevent incorporating greedy methods.

We tried to formulate this as a mixed integer programming problem, to take advantage of the smart heuristics that have been incorporated within that field, but the problem does not fit nicely (mostly due to the fact that we want to minimize the result of a set of min operators; this requires for each cell an additional integer variable + constraint).

As the problem formulation seems fundamental and elegant enough, I was wondering if other people have came across a similar problem? Are there scientific publications that describe the problem, heuristics or approximations to solve the problem?

Thanks in advance!

Community
  • 1
Jan N. van Rijn
  • 21
  • It is a typical problem to be handled with dynamic programming. See Applied Dynamic Programming - Richard Bellman & Stuart Dreyfus - Princeton University Press. – Cesareo May 30 '18 at 18:51
  • Thanks for the suggestion. However, to all it seems, in order to break down the problem in smaller subsets the amount of required memory seems to grow exponentially. Currently I apply a variation on branch and bound with some clever tricks to solve the problem in an exponential manner. – Jan N. van Rijn Jun 01 '18 at 18:48
  • I finally found out the most related problem, which is the Maximum coverage problem: https://en.wikipedia.org/wiki/Maximum_coverage_problem. The problem seems to be NP-hard and the greedy solution seems to be submodular – Jan N. van Rijn Oct 18 '18 at 19:30

0 Answers0