Maximum number of matched vertexes in a one-to-many bipartite graph

Question

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who are satisfied. A bidder is satisfied if he gets all the items that he bid for in the first place. For eg-

Bidders = A,B,C
Items = 1,2,3,4

Bidder    Bids
A         1,2
B         2,3
C         3,4

In this case its only possible to satisfy 2 bidders at max.

I've tried to model the problem to a maxflow problem and have taken several approaches but to no avail My approaches so far-

1. Tried to model this problem as a bipartite matching problem. The only problem being that instead of a one-one mapping I have a one-many mapping with an AND condition.

2. A maxflow problem with edges going from source to each vertex with a capacity of number of bids. Problem here being ensuring that all edges from a bidder are selcted.

3. A maxflow problem with both upper bounded and lower bounded edge capacities.

Answer 1

Since your problem is exactly the set packing problem, it is NP-hard. However, you only have $n = 20$ bidders, so you can solve it using a simple exponential algorithm:

1. For every item $i$, build the subset $B_i$ of bidders that bid for it. You can represent this subset for example as a bitmask. You know that for all $i$, every subset $S \subset B_i$ with $|S| > 1$ can not be a subset of the solution.
2. For all $B_i$, enumerate all of its "forbidden" subsets of size > 1 and store them. Avoid revisiting already stored subsets by using recursion and memoization, by canceling the bits one after another.
3. Go through all subsets of bidders. For every set, check whether it has a a forbidden subset. You can use the same recursive algorithm as in step 2.

Note that if you only enumerate subsets of size 2 in step 2, you have reduced your problem to an independent set problem in a graph with $n$ nodes, so you can apply any other more efficient algorithm to it.

Runtime: $O(n \cdot (2^n + m))$, with $m$ being the number of items and $n$ being the number of bidders. With a good independent set algorithm you can get something like $O(m \cdot n^2 + 1.3^n)$

Answer 2

This problem can be reduced to the maximum independent set problem:

We use the fact that if $A$ and $B$ bid for the same item, then $A$ can be satisfied if and only if $B$ is not satisfied, and thus we construct a new graph:

The vertex set $V$ represents all the bidders, and we connect with an edge any pair of bidders that have any common bid.

Note that this is a general graph, and it's not bounded in any way (we can create any general graph with the input of your problem)

The maximum independent set in this graph represents maximum number of satisfied bidders. In order to get the actual matching, you can save the list of wanted items in each vertex, and translate the maximum independent set to a matching.

Unfortunately this problem is $NP-Hard$, but many good approximation algorithms and heuristics are available.

Answer 3

Ron Teller's answer is probably the best, but here is one additional way you could try to solve it in practice: you could formulate this as a zero-or-one integer linear program.

In particular, introduce one (zero-or-one integer) unknown $x_i$ for each bidder, where $x_i=1$ means that bidder $i$ gets all his items and $x_i=0$ means that bidder $i$ doesn't get anything. Now you can formulate the requirement that no item is chosen by more than one bidder as follows: if bidder $i$ and $j$ both require the same element, introduce the constraint $x_i + x_j \le 1$. Finally, your objective function is the sum of the $x_i$'s, and you want to maximize this. You could feed this to an off-the-shelf ILP solver, and see how it does. With only 20 bidders, my guess is that they will solve this kind of problem easily.

Of course, with only 20 bidders, another feasible solution is to simply enumerate all possible subsets of the 20 bidders, and check which ones satisfy your constraints. There are only one million of them, so this is probably viable... However, the ILP solution will probably scale better.