[Numpy-discussion] Linear assignment problem: Jonker-Volgenant algorithm

[josef.pktd at gmail.com]

On Mon, May 16, 2011 at 8:53 AM, Charles R Harris
<charlesr.harris at gmail.com> wrote:
>
>
> On Mon, May 16, 2011 at 1:18 AM, Gael Varoquaux
> <gael.varoquaux at normalesup.org> wrote:
>>
>> Following a suggestion by Joseph, I am trying to implement the
>> Jonker-Volgenant algorithm for best linear assignment in Python, using
>> numpy. Unsuprisingly, it is proving time-costly. I cannot afford to spend
>> too much time on this, as it not to solve a problem of mine, but for the
>> scikits.learn. Thus I was wondering if someone had a BSD-licensed Python
>> version of the algorithm that he would be willing to share.
>>
>
> I was at a presentation two weeks ago where open source software for linear
> assignment was referenced, so I think some is available, although that part
> went by so quickly I might have missed something. I still don't know what
> linear assignment does, but that is another problem...

OT for the implementation question:
linear assignment in the simplest case is just optimal matching of
pairs, male-female, seller-buyer, where each side has full ranking
preferences about being matched with anyone on the other side.

more general case, college and student matching, or interns and
hospitals, where one side has a capacity to be matched with more than
one from the other side.

(more fun if you allow for side-payments, i.e. prices)

Josef


>
> Chuck
>
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>