An award committee’s job is to award n prizes to m candidates. Each prize is a

Question

An award committee’s job is to award n prizes to m candidates. Each prize is associated with
a list of candidates who are qualified to receive the prize. There is however an upper bound k
on the number of prizes each candidate can receive. Design an efficient algorithm that given n
and m, the list of qualified candidates for each of the n prizes, and the upper bound k, awards
the n prizes to the m candidates so as to maximize the number of prizes awarded. Analyze the
running time and show the correctness of your algorithm.

Explanation / Answer

This is a classic network flow problem.

we draw a bipartite graph.

the vertex set = {all the candidates, all the prizes}

edge set = {(candidate i , prize j, capacity = 1) is a one way edge if candidate i can be given prize j}

we have one source and one sink

some edges = {(source, candidate i, capacity = 1) for all i}

some edges = {(prize i, sink, capacity = 1) for all i}

Now we have this graph, we just apply a max flow algorithm on it look for many of them

the complexity O(V^3) = O((m+n)^3)

http://en.wikipedia.org/wiki/Maximum_flow_problem

here are the algorithms

comment if you have any doubts

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.