Pairing Problem

[arush]

I have the following assignment problem for which i have already
formulated an integer linear program. I was wondering if there is a
known algorithm for solving the problem. A reduced version of the
problem is as follows:

I have six balls {s1,s2,s3........s6} and three boxes{Box1,Box2,Box3}.
I have to assign a box to each ball. for example (s1,s3) ---> Box 2,
(s2,s4) ----->Box1 and so on. Pairing these balls has a cost assigned
to it represented by cost(i,j) forall i,j = 1,2,3,4,5,6.

I have to pair up the balls in such a way that i incur the minimum
cost. Is there any know solution for this problem.

Thanks
Arush.

[Paul Rubin]

Search for "weighted matching problem". There are indeed known
algorithms. The base case, a bipartite graph, does not apply here, but
there are algorithms (well, at least one for sure) for the nonbipartite
(if that's a word) case.

/Paul

[arush]

Hello Rubin,
I did think of the maximum weight on a regular graph. The problem with
that i suppose is that the maximum weight on a graph may result in
selecting just a subset of nodes. (in my case the six balls
s1,s2,s3,....s6 ) . I need to make sure that every ball is placed in a
box.
Arush.

[Paul Rubin]

No, I meant what I said: "weighted matching problem". The matching
problem pairs nodes (connected by edges) in a graph so as to maximize
the number of paired nodes (equivalently, the number of selected edges)
without having two or more edges incident on a single node. The
weighted matching problem maximizes the sum of the weights of the
selected edges, rather than the number of selected edges.

[arush]

Hello Rubin,
So the weighted matching problem maximizes the sum of the weights of
the
selected edges, rather than the number of selected edges. Since i want
all the nodes to be selected does that imply that i would look out for
the maximum matching .

[Paul Rubin]

Assuming all your weights are positive. (Doesn't work with negative
weights.)