[Solved]: Maximum number of matched vertexes in a one-to-many bipartite graph

Problem Detail: 

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.

Asked By : TestUser5

Answered By : Niklas B.

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)$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22542