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-
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.
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.
A maxflow problem with both upper bounded and lower bounded edge capacities.