There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items sold. So, the shopkeeper needs to maximize the number of buyers. The buyers will buy only if all the items are being sold. Items are unique. All items need not be sold.So, basically, we have a bipartite graph. We need to find a set of edges which maximize the number of nodes on Buyer vertex set such that each node on item set has only one edge. Any suggestions?
How to maximize the number of buyers in a shop?
graph theory;greedy algorithms;bipartite matching