Re: Is this an optimal solution?

On Oct 13, 4:00 pm, Tor Myklebust <tmykl...@xxxxxxxxxxxxxxxxxxx>
wrote:
Tonny <tonnysp...@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

Hello Tor,

Thank you so much !! Yep, it's broken.

Okayz, It's time for me to think more about it.

Thanks again.

Tonny Tao

.