An agent is works between n producer and m consumers. ith producer, generates s_i candy and jth consumer consumes b_j candy in this year. For each candy that sales, agent get 1 dollar payoff. For some problems, one strict rule was defined that a producer should be sales candy to any producer that the distance between them is not greater than 100 KM (kilometers). if we have list of all pairs of producer-consumer that the distance between them is lower than 100 KM, which of the following algorithm is goof for finding maximum payoffs? (suppose s_i and b_j may be becomes very large).
1) Maximal Matching
2) Dynamic Programming
3) Maximum Flow
4) 1 , 3
this is a last question on 2013-Final Exam on DS course. Any hint or idea?
To my understanding, the problem can be solved as a Maximum Bipartite Matching, however the modelling requires the graph to be relatively large compared to the original input; for every feasible edge (s_i,b_j) introduce s_i nodes for the producer partition and b_j for the consumer partition and connect each producer node of the to each consumer node of them.
The problem can be modelled as Maximum Flow Problem on a bipartite graph, however; the flow on each feasible edge (s_i,b_j) is constrained by 0 from below and min{s_i,b_j} from above, as the flow must be nonnegative, but may exceed neither the producer's nor the consumer's capacity.
Concerning a solution via Dynamic Prgramming, consider the following sketch of a recurrence relation for Maximum Bipartite Matching. Let n and m denote the number of nodes in the first and second partition, respectively. Fix a node a in the first partition; either a is not matched or matched to one of its neighbors; in either case, each possibility is evaluated, recursively evaluating an instance where the partitions have n-1 and m or n-1 and m-1 nodes, respectively; the best of these choices is taken.
To put it all in a nutshell, apparently all of the proposed approaches yield valid solutions; however, the modelling as network flow seems to be most natural.
