Re: Is this an optimal solution?

As Jym has already pointed out, the problem is one of finding
matchings. But it's not a perfect matching that you are looking for...
it's actually a maximum matching in a bipartite graph. This problem is
solvable in O(V^2 E) using the Hungarian algorithm.
http://en.wikipedia.org/wiki/Hungarian_algorithm#Bipartite_graph_representation
HTH
Navneet

On Oct 13, 12:37 pm, Jym <Jean-Yves.Moyen+n...@xxxxxxxxxxxx> wrote:
On Sat, 13 Oct 2007 02:48:08 +0200, Tonny <tonnysp...@xxxxxxxxx> wrote:
Suppose that each person looking for a job is interviewed by multiple
employers. The
interview is successful if both the candidate wants to work for the
employer and the employer wants to employ the candidate. For each
candidate we are given list of the successful interviews. We want to
assign as many people as possible to jobs. Every employer is going to
employ only one person and we can assign a person to a job only if the
person had a successful interview for the job.

Here is one possible algorithm:
Discard all candidates who do not have a successful interview. Choose
the candidate with the smallest number of successful interviews. From
his/her potential employers, choose the
employer that has the smallest number of successful interviews.
Choices are made in an arbitrary fashion if there is a tie for the
smallest number. Assign this person to the employer, remove all
interviews involving either of them and repeat (recalculating the
number of successful interviews).

I was wondering if this is really an optimal solution. Any idea would
be greatly appreciated.

Have you looked at the problem caled "perfect matching" ?
This is basically the same thing execpt you have an ordering of choice
(each candidate has an ordered list of jobs he wants, each employer has en
ordered list of candidate he wants).
Your problem looks like a special case of perfect matching.

--
Hypocoristiquement,
Jym.


.