CODEWITHSUNDEEP
algorithmcomputer-science
srinu
srinu

Reputation: 9

Polynomial time user pairing algorithm

i have a problem . Consider users with different weights which depends on present channel .i.e. if the channel is good weights are high. I had to pair the users in such a way that total weight of the system should be maximum. I will elaborate this. Consider 4 channels and 8 users , now i have to place the paired users in each channel such that sum total of weights is maximum and all users are to be paired. Please suggest some polynomial time algorithms other than optimal(brute force) which becomes complex when number of users are large,which would be of great help to me.

Thanks and regards, srinu.

Upvotes: 0

Views: 121

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Vladimir Kolmogorov published Blossom V: a new implementation of a minimum cost perfect matching algorithm in 2009 which provides a polynomial algorithm for the "problem of computing a perfect matching of minimum cost in an undirected weighted graph."

Changing to maximum cost is trivial by changing the sign of your weights.

This algorithm has a worst case complexity O(n^3m) (but is often much faster for typical examples). n is the number of nodes, and m the number of edges. In your case I believe all n^2 edges are present, so the complexity is O(n^5).

There are faster algorithms if your graph is bipartite (e.g. users fall into two categories such as male and female where you must always match a male with a female) but I don't believe that is the case for you?

A software implementation of this algorithm is here.

Upvotes: 1

Related Questions