<p>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).</p>

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

<p>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.</p>

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

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

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

<p>[1] <em>Assignment Problems</em> by Rainer Burkard, Mauro Dell'Amico, Silvano Martello</p>

CC BY-SA 2.5
2010-09-05T02:07:24.760Z
I think this works. Can you give a reference for the O(n^2.5)-time algorithm?
Serge Gaspers
CC BY-SA 2.5
2010-09-05T07:16:37.737Z
@Serge, I've edited my answer to include references
Tomer Vromen
CC BY-SA 2.5
2010-09-05T10:53:33.223Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-05T00:56:06.480Z
2010-09-05T07:16:01.077Z
2010-09-05T07:16:01.077Z
Tomer Vromen
<p>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.</p>

<hr>

<p>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".</p>

<p>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.</p>

<p>[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). <a href="http://eprints.gla.ac.uk/15/" rel="nofollow">Postprint</a>.</p>

CC BY-SA 2.5
2010-09-04T16:51:07.003Z
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.
Neeldhara
CC BY-SA 2.5
2010-09-05T01:08:46.047Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-04T15:59:31.840Z
2010-09-05T02:06:12.670Z
2010-09-05T02:06:12.670Z
Serge Gaspers
<p>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.</p>

<p>If this understanding is correct, I would think that an augmenting path algorithm similar to Busacker–Gowen [<a href="http://books.google.com/books?id=NvuFAglxaJkC&amp;pg=PA299" rel="nofollow" title="1">1</a>] 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).</p>

<p>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.)</p>

CC BY-SA 2.5
2010-09-07T13:31:30.673Z
2010-09-07T13:31:30.673Z
Magnus Lie Hetland
<p>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.)</p>

CC BY-SA 2.5
2010-09-06T21:10:23.297Z
Seems to be the same solution as in Tsuyoshi Ito's comment to Tomer Vromen's answer?
Jukka Suomela
CC BY-SA 2.5
2010-09-06T21:26:21.700Z
Does your algorithm generalize to the case where each person indicates a set of desirable attributes and a set undesirable attributes?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-06T18:27:18.440Z
2010-09-06T18:27:18.440Z
Noam
<p>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.   </p>

<blockquote>
  <p>Is finding a matching with maximum satisfaction efficiently solvable or is it $NP$-hard? </p>
</blockquote>

CC BY-SA 2.5
2011-01-31T15:33:25.020Z
Is the average number of attributes satisfied a better measure of satisfaction than the number of attributes satisfied for the least lucky person?
Dónal
<cc.complexity-theory><np-hardness><matching>
Complexity of marriage matching problem?
Mohammad Al-Turkistany
# Complexity of marriage matching problem?

(Asked by: username_0 on 2010-09-04)

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?

**Tags:** cc.complexity-theory, np-hardness, matching

> **Comments:**
> **username_1**: Is the average number of attributes satisfied a better measure of satisfaction than the number of attributes satisfied for the least lucky person?  

---

## 4 answers

### Answer by username_7 on 2010-09-06. Score: 7 | Accepted answer

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.)

> **Comments:**
> **username_8**: Seems to be the same solution as in username_4's comment to username_2's answer?  
> **username_0**: Does your algorithm generalize to the case where each person indicates a set of desirable attributes and a set undesirable attributes?  

---

### Answer by username_2 on 2010-09-05. Score: 7

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

> **Comments:**
> **username_3**: I think this works. Can you give a reference for the O(n^2.5)-time algorithm?  
> **username_2**: @Serge, I've edited my answer to include references  
> **username_4**: 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.  

---

### Answer by username_3 on 2010-09-04. Score: 3

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](http://eprints.gla.ac.uk/15/).

> **Comments:**
> **username_5**: 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.  
> **username_4**: 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.  

---

### Answer by username_6 on 2010-09-07. Score: 0

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](http://books.google.com/books?id=NvuFAglxaJkC&pg=PA299 "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.)


---

