3
$\begingroup$

I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all guy-girl matchings/'edges' are possible, and the edges are weights. Also, I'm not looking for a perfect solution - just a reasonable approximation where most people get as close as possible to 5 matches.

Any idea how to go about it? The traditional stable marriage and assignment solutions don's work in this case.

p.s For context: the real world problem is matching users to girls/guys in their extended social network.

$\endgroup$
  • $\begingroup$ When there are G1 ... G5 ... and g1 ... g5 ..., at least five of each, then G's can select g1 ... g5, and g's can select G1 ... G5. Simple. Except that it's not what you want. Then what do you? $\endgroup$ – Włodzimierz Holsztyński Oct 27 '14 at 22:46
  • $\begingroup$ What is your objective function? Maximize the weighted matching? (Then max-flow should work, right?) Or do you actually want a stable solution, or just any feasible solution, or.... $\endgroup$ – usul Oct 28 '14 at 1:04
  • 1
    $\begingroup$ @usul - The objective is to maximize the weight. Wouldn't I need a Minimum-cost flow or Hungarian method to solve this? $\endgroup$ – EugeneMi Oct 28 '14 at 20:20
  • $\begingroup$ I think you're right, max-flow doesn't work. But something like the Hungarian algorithm should, or using an LP as Robert Israel suggests might be the fastest. $\endgroup$ – usul Oct 28 '14 at 23:10
8
$\begingroup$

You can do this as a weighted network-flow problem where each guy is a source of $5$ units, each girl is a sink of $5$ units, and each possible arc has capacity of $1$ unit. You can solve it using linear programming, and the integrality theorem guarantees that a basic optimal solution is in integers.

$\endgroup$
  • $\begingroup$ Thanks Robert! I'm not particularity good with linear programming. What would be the space/time complexity of such a solution? (I'm trying to compare it to combinatorial algorithms such as Ford–Fulkerson algorithm) $\endgroup$ – EugeneMi Oct 29 '14 at 13:29
  • 1
    $\begingroup$ I don't know the complexity of the currently best algorithms for network flow optimization. I think it may depend on what assumptions can be made about the weights. But in practice, if the choice is between implementing a network flow algorithm yourself and using linear programming software such as Cplex that is highly optimized for modern CPU's, the linear programming software is likely to be faster even though the network flow algorithm is theoretically better. $\endgroup$ – Robert Israel Oct 29 '14 at 16:41
  • $\begingroup$ Isn't it an integer linear programming problem (which is much harder than LP)? Also, it's very possible that a solution does not exist since note all nodes are connected to each other - how do I handle it in LP? $\endgroup$ – EugeneMi Oct 30 '14 at 14:07
  • $\begingroup$ No, it's a linear programming problem. The coefficient matrix is totally unimodular, and the b vector has integer entries, so every basic solution is in integers. If no solution exists, the LP will be infeasible. $\endgroup$ – Robert Israel Oct 30 '14 at 15:38
  • $\begingroup$ really appreciate your help! Linear Algebra has never been my forte... If the problem is formulated as min-cost max flow it is possible to not have a solution (max flow). But I can formulate the problem as a Maximum Weight Matching and then just add nodes with 0-weight/capacity edges. $\endgroup$ – EugeneMi Oct 30 '14 at 16:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.