Re: Is this an optimal solution?

Tonny <tonnyspain@xxxxxxxxx> wrote:
On Oct 13, 3:47 am, byte_me <nav...@xxxxxxxxx> wrote:
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_repr...
HTH
Navneet

The Hungarian method is overkill for unweighted problems.

Thank you guys for reply. I know it's a maximum bipartite matching
problem, what I wonder is if this algorithm can generate an optimal
solution. Any suggestion?

No; it's broken. Consider:

1-1, 2-2, 3-3, 4-4, 5-5, 1-2, 2-1, 3-2, 4-3, 4-5, 5-3, 5-4.

There is obviously an assignment of dudes to jobs so that everyone gets
a job and every job is filled. Everyone has at least two successful
interviews. 1, 2, and 3 have exactly two successful interviews. Let's
give 3 a job. Both of 3's potential jobs have three successful
candidates, so let's give dude 3 job 2. We're suddenly screwed; dudes 1
and 2 are competing for job 1 but only one of them can get it.

Slightly bigger examples of this kind will break "better" versions of
this heuristic.

Tor Myklebust
.

Relevant Pages

  • Re: Is this an optimal solution?
    ... On Oct 13, 4:00 pm, Tor Myklebust ... But it's not a perfect matching that you are looking for... ... There is obviously an assignment of dudes to jobs so that everyone gets ... 1, 2, and 3 have exactly two successful interviews. ...
    (comp.theory)
  • Re: Is this an optimal solution?
    ... But it's not a perfect matching that you are looking for... ... employer and the employer wants to employ the candidate. ... assign as many people as possible to jobs. ... the candidate with the smallest number of successful interviews. ...
    (comp.theory)