Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair binds one male to one female. The satisfaction of a matching is number of attributes satisfied for the least lucky person.

Is finding a matching with maximum satisfaction efficiently solvable or is it $NP$-hard?

  • $\begingroup$ Is the average number of attributes satisfied a better measure of satisfaction than the number of attributes satisfied for the least lucky person? $\endgroup$ – Dónal Jan 31 '11 at 15:33

Let's start with the decision version of the problem: given a "satisfaction level" k, does there exist a matching where everyone gets matched to a person with at least k desired attributes. This is just solving bipartite matching on a graph where we connect a male and a female if each gets satisfaction k from the other. (Running time seems like O(mn^2).) To get the original problem, just do a binary search over k (for an extra log(m) factor in running time.)

  • $\begingroup$ Seems to be the same solution as in Tsuyoshi Ito's comment to Tomer Vromen's answer? $\endgroup$ – Jukka Suomela Sep 6 '10 at 21:10
  • $\begingroup$ Does your algorithm generalize to the case where each person indicates a set of desirable attributes and a set undesirable attributes? $\endgroup$ – Mohammad Al-Turkistany Sep 6 '10 at 21:26

I may have misunderstood the question, because my answer conflicts with Serge's. To my understanding, you're asking about the Linear Bottleneck Assignment Problem. This is known to be solved in O(n^2.5).

The most complete source of information is [1], although I really don't like the book's style. There's also a website: http://www.assignmentproblems.com/linearBNAP.htm

EDIT: To clarify, the we want an assignment such that the edge with maximal cost is minimized. The cost will be the maximal number of unassigned attributes for either the man or the woman that are matched.

EDIT2: I can only offer references from the book I cited. Three of them are:

  1. G. Carpaneto and P. Toth Algorithm for the solution of the bottleneck assignment problem. Computing, 27:179-187m 1981
  2. U. Derigs. Alternate strategies for solving bottleneck assignment problems - analysis and computational results. Computing, 33:95-106, 1984
  3. U. Derigs and U. Zimmermann. An augmenting path method for solving linear bottleneck assignment problems. Computing, 19:285-295, 1978

You should try to get hold of the book, since lists some of the available algorithms.

[1] Assignment Problems by Rainer Burkard, Mauro Dell'Amico, Silvano Martello

  • $\begingroup$ I think this works. Can you give a reference for the O(n^2.5)-time algorithm? $\endgroup$ – Serge Gaspers Sep 5 '10 at 2:07
  • $\begingroup$ @Serge, I've edited my answer to include references $\endgroup$ – Tomer Vromen Sep 5 '10 at 7:16
  • 2
    $\begingroup$ By the way, if we are satisfied with a slower algorithm, it is easy to solve the “Linear Bottleneck Assignment Problem” (I did not know the name, why “Linear”?) in polynomial time by using binary search and solving the perfect matching problem in each iteration. $\endgroup$ – Tsuyoshi Ito Sep 5 '10 at 10:53

As Tsuyoshi points out in a comment below, there is no reason why a solution to the problem has to be a stable matching. So, the approach of this answer does probably not work; especially since I believe that Tomer's answer is correct.

It seems that your version of the Marriage problem is equivalent to the Minimum regret Stable Marriage problem with Ties, where everybody ranks the members of the other sex with possible ties, and the goal is to maximize the minimum "happiness".

It is shown in [1] that Minimum regret Stable Marriage problem with Ties is not approximable within $N^{1-\epsilon}$, for any $\epsilon > 0$, unless P=NP, where $N$ is the number of men in a given instance of the problem, even if the ties are on one side only, there is at most one tie per list, and each tie is of length 2.

[1]: David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita: Hard variants of stable marriage. Theor. Comput. Sci. 276(1-2): 261-279 (2002). Postprint.

  • 1
    $\begingroup$ Indeed, I think you can convert the given problem to the min-regret situation: if a member has $S$ desirable attributes, then the ranking will be in decreasing order of $|S \cap A_i|$, where $A_i$ is the set of attributes of person $i$, $i$ ranging over members of the opposite gender. $\endgroup$ – Neeldhara Sep 4 '10 at 16:51
  • 1
    $\begingroup$ I cannot see why a solution in the asked question has to be a stable matching, although I have not understood the asked question completely. $\endgroup$ – Tsuyoshi Ito Sep 5 '10 at 1:08

Isn't this just a variation of min-cost maximum bipartite matching? The weight for each edge equals the number of satisfied attributes, and instead of finding the maximum matching that gives you the smallest weight sum, you want the one for which the minimum edge weight is maximized.

If this understanding is correct, I would think that an augmenting path algorithm similar to Busacker–Gowen [1] would work. Instead of always finding the cheapest augmenting path (in terms of weight sum), you would find the best one (maximizing the minimum edge). That, again, should be doable with a slight modification to any standard shortest-path algorithm (such as Dijkstra's, which is used in the version of Busacker–Gowen using the weight adjustment of Edmonds and Karp).

I guess you'd have to re-work the correctness proof, but I'd think it should work? The running time for an optimum flow with flow value v (that is, v matched pairs in this case) would be $O(v|E|\lg |V|)$ in the general case; here I guess that would be $O(vn^2\lg n)$, although it might be even lower for the specific application to bipartite matching. (Busacker–Gowen is a general min-cost flow algorithm.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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