I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed some paper or help analyze the problem?

Consider two sets of nodes, $U$ and $V$. $f_u(v)$ is the non-negative (integer) preference function of $u\in U$ towards $v\in V$. Similarly, $f_v(u)$ is for $v\in V$ towards $u\in U$. Let $E\subseteq U\times V$ be a set of pairs. Each pair $(u,v)\in E$ indicates that we can never allocate one to the other.

$\pi$ is an allocation where $\pi(u)\in V$ is the node allocated to $u$ and $\pi(v)\in U$ is the node allocated to $v$. $\pi$ is weak-stable if there does not exist a pair ($u,v$) such that $f_u(v)>f_u(\pi(u))$ and $f_v(u)>f_v(\pi(v))$, which means that $u$ prefers $v$ to $\pi(u)$ and $v$ prefers $u$ to $\pi(v)$ simultaneously.

I want to compute a stable matching with maximum size, i.e. $maximize_{\pi}|\pi|$. Notice that, ties are allowed in any preference function.

  • $\begingroup$ It seems to me that your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). Am I missing something? $\endgroup$ Oct 5 '16 at 16:02
  • $\begingroup$ @HirokiYanagisawa Many thanks! I find the MAX SMTI problem in Hard Variants of Stable Marriage. They show that this problem is NP-hard and give a 2-approximation algorithm. $\endgroup$ Oct 5 '16 at 18:35
  • $\begingroup$ @HirokiYanagisawa I see more than 200 papers citing it, I am wondering if you know any paper solves the weighted version, i.e. instead of simply maximizing $|\pi|$, I wish to $maximize_{\pi}\sum_{(u,v)\in \pi}f_u(v)$. I guess there will also be a 2-approximation on the weighted version. $\endgroup$ Oct 5 '16 at 18:36
  • $\begingroup$ I notice that there is a paper Stable Marriage with Incomplete Lists and Ties. This paper works on minimizing a particular cost (or called preference index), but not the weight I wish to maximize -- the mathmatical things are different. $\endgroup$ Oct 5 '16 at 18:41
  • $\begingroup$ I posted my comment in the answer section. $\endgroup$ Oct 6 '16 at 14:44

Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). You can find the current best approximation algorithm for MAX SMTI in the following paper: Z. Kiraly, Linear Time Local Approximation Algorithm for Maximum Stable Marriage, Algorithms 2013, 6, 471-484.

There are many papers on MAX SMTI, but unfortunately I am not aware of any paper that handles the weighted version of MAX SMTI.


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.