# Re: Is this an optimal solution?

*From*: Tonny <tonnyspain@xxxxxxxxx>*Date*: Sat, 13 Oct 2007 15:36:47 -0700

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

.

**References**:**Is this an optimal solution?***From:*Tonny

**Re: Is this an optimal solution?***From:*Jym

**Re: Is this an optimal solution?***From:*byte_me

**Re: Is this an optimal solution?***From:*Tonny

**Re: Is this an optimal solution?***From:*Tor Myklebust

- Prev by Date:
**Re: CFG** - Next by Date:
**Orientation of rotationally invariant bit vectors** - Previous by thread:
**Re: Is this an optimal solution?** - Next by thread:
**CFG** - Index(es):