0

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?

1 Answer 1

1

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.

14
  • 1
    what do you mean by sd the flow must be nonnegative?
    – user4554402
    Feb 12, 2015 at 10:11
  • 1
    In fact, you can use maximum bipartite matching by using more nodes. For a producer with s_i candy, create s_i nodes, and do the same thing for the consumers.
    – Yu-Han Lyu
    Feb 12, 2015 at 14:31
  • Thanks for the hint, I will clarify my answer.
    – Codor
    Feb 12, 2015 at 14:41
  • It was a typo; I meant that the flow assigned to each edge must be nonnegative.
    – Codor
    Feb 12, 2015 at 19:01
  • Dear @Codor, which of them is more efficient?
    – user4554402
    Feb 12, 2015 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.