According to the paper you linked, the problem of finding a maximum
cardinality weakly stable matching is NP hard. That means that you
are not going to find an exact and fast algorithm to solve the
problem, assuming you need to match as many people as possible
(maximum cardinality). You will have to approximate or use a
heuristic approach. The paper mentions that every weakly stable
matching can be turned into a stable matching by selecting some set of
preferences for the ties list. Since there is an algorithm for
finding a stable matching for roommates, you could try randomly
assigning preferences. Note however that this strategy may not be
helpful, as another paper
http://www.dcs.gla.ac.uk/publications/PAPERS/7953/blockingpairs.pdf
(involving one of the authors of this one) indicates that you won't be
able to find a maximal matching for the stable roommates problem, so
you won't have any guidance when you set up the random preference
assignment.
I think this research tells us that you should choose a different
model for your problem if possible. If roommates are either
acceptable or unacceptable with no preferences otherwise, the problem
becomes the classical matching problem on nonbipartite graphs, which
can be solved in polynomial time. Weighted versions are also possible
in slower time, but still polynomial. For this version, every pair of
people must have either a preference or an aversion which is shared
among the pair, and your desire is to maximize the sum of all
individual pairs' happiness. (To keep from picking people who
absolutely hate each other, these pairs can have a negative weight of
value greater than the sum of all positive weights. Then the pair
will only be paired if absolutely necessary.) Descriptions of these
algorithms can be found in "Combinatorial Optimization: Algorithms and
Complexity" by Papadimitriou and Steiglitz. |
