Is this an optimal solution?
- From: Tonny <tonnyspain@xxxxxxxxx>
- Date: Fri, 12 Oct 2007 17:48:08 -0700
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.
Thanks.
.
- Follow-Ups:
- Re: Is this an optimal solution?
- From: Jym
- Re: Is this an optimal solution?
- Prev by Date: Re: I'm confused: Turing machine model vs. interactivity
- Next by Date: Re: Is this an optimal solution?
- Previous by thread: I'm confused: Turing machine model vs. interactivity
- Next by thread: Re: Is this an optimal solution?
- Index(es):
Relevant Pages
|
