CODEWITHSUNDEEP
algorithmmatchingbipartite
user3091275
user3091275

Reputation: 1023

How can I get optimal matching between K groups?

I have K sets of data points, I would like to make groups of size K which minimize the total sum of intra group distances. I'm familiar with matching algorithms with bipartite graphs, but I would like this for more than two sets.

Any ideas?

Edit :

Each group would be made of one element of each set, no repetitions allowed.

An example : you have {a1, a2, a3}, {b1, b2, b3}, {c1, c2, c3} You want to create groups e.g. {a1, b3, c3}, {a2, b1, c2}, {a3, b2, c1} minimizing the sum of intra group distances.

Upvotes: 5

Views: 147

Answers (2)

Dillon Davis
Dillon Davis

Reputation: 7740

This problem can be reduced to another, similar problem that I have solved for another stackoverflow question before. The idea is to compute all combinations of n / k sized groups, and weight these according to their intra group distances. Traverse the search space for valid combinations of combinations. Keep record of the minimal sum, and use this to prune dead-end branches. You can speedup the search using dynamic programming by producing optimal subsets of the solution, and building up to the final solution from that (as described in my other post), or you could use a greedy method and some hand wavey tricks to find a nearly optimal (or optimal) solution (also described in said post). Here is a link to the sub problem that you can reduce this to.

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65458

Even for k=3 it has the flavor of the NP-hard problem 3-dimensional matching. (The obvious reduction doesn't work because there may be phantom triples created where each of the three pairs of an invalid triple appears separately in a valid triple.)

Depending on the size of the instance, I would either try local search or integer programming with column generation (but the inner problem seems hard without the structure of a low dimensional metric space, and nontrivial even then).

Upvotes: 0

Related Questions