Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.)
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:
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
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.
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.)
