Re: Is this an optimal solution?
- From: Jym <Jean-Yves.Moyen+news@xxxxxxxxxxxx>
- Date: Sat, 13 Oct 2007 09:37:07 +0200
On Sat, 13 Oct 2007 02:48:08 +0200, Tonny <tonnyspain@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.
.
- Follow-Ups:
- Re: Is this an optimal solution?
- From: byte_me
- Re: Is this an optimal solution?
- References:
- Is this an optimal solution?
- From: Tonny
- Is this an optimal solution?
- Prev by Date: Is this an optimal solution?
- Next by Date: Re: Is this an optimal solution?
- Previous by thread: Is this an optimal solution?
- Next by thread: Re: Is this an optimal solution?
- Index(es):
Relevant Pages
|
