2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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$
    – Hiroki Yanagisawa
    Oct 5, 2016 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$
    – user2789928
    Oct 5, 2016 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$
    – user2789928
    Oct 5, 2016 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$
    – user2789928
    Oct 5, 2016 at 18:41
  • $\begingroup$ I posted my comment in the answer section. $\endgroup$
    – Hiroki Yanagisawa
    Oct 6, 2016 at 14:44

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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