I am trying to solve a real-world problem that I was able to reduce to the problem described below. I would like to know the following things:

  1. Is there literature about this problem?
  2. Is the corresponding decision problem NP-complete?
  3. Do you know an efficient algorithm to solve the problem?
  4. If not, what would be a good technique to solve it approximately?

The problem is as follows. Given a $n \times m$ matrix $M$ with entries in $[0, 1]$, and a function $a \colon \{1, \ldots m\} \to \mathbb{N}$. For each column $j$, we want to pick $a(j)$ entries in that column, such that in each row, at most one element was picked. We want to do this in such a way that the sum of the picked values is maximized.

More formally, find a function $T\colon \{1, \ldots n\} \to \{1, \ldots m\} \cup \{\bot\}$ which maps each row to a column (or $\bot$), with the following two properties:

  1. $\forall j \in \{1, \ldots m\} \colon \lvert T^{-1}(j)\rvert = a(j)$
  2. The following expression is maximized: $$ \sum_{\substack{i=1 \\ T(i) \neq \bot}}^n M_{i, T(i)} $$

Of course, you could also define it the other way around, with each column mapping to a set of rows. Finally, the corresponding decision problem is in NP, as the function $T$ acts as a certificate. I tried a reduction to knapsack, as the two seem quite similar, but I was unsuccessful.


Reduce to maximum-weight bipartite matching.

If you just wanted ​ for each j, pick at most a($\hspace{.015 in}$j) entries from the j-th column ,
then the reduction would be

One of the parts is ​ ​ ​ one vertex for each row.
The other part is ​ ​ ​ for each j, a($\hspace{.015 in}$j) vertices for the j-th column .
The weight of each edge is the corresponding matrix entry.

and the reasoning would be

The ​ one vertex per row ​ ensures that at most one element will be picked for each row.
The ​ a($\hspace{.015 in}$j) vertices for the j-th column ​ allows the j-th column to be
used a($\hspace{.015 in}$j) times but prevents it from being used more than that.
The weights of the edges make the total weights of the matchings
correspond to your objective function.


For ​ for each j, pick exactly a($\hspace{.015 in}$j) entries from the j-th column , ​ you'd do:

Check whether-or-not ​ ​ ​ n ​ < ​ a(1) + a(2) + a(3) + ... + a(m-1) + a(m) ​ .

If that inequality is true, then there are no feasible solutions.

Otherwise, construct the bipartite graph like above but letting the edge weights be
a(1) + a(2) + a(3) + ... + a(m-1) + a(m) + 1 ​ + ​ the corresponding matrix entry ​ .
This will make it so that all maximum-weight matchings use the whole column part,
thereby indicating exactly a($\hspace{.015 in}$j) entries for each j-th column.


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.