I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, the agents of $S_2$ have the same preference list. The stability constraints can be modelled as follows:

$ 1 \leq \sum\limits_{j'\in F^{\leq}_{j}(i)}x_{ij'} + \sum\limits_{i'\in C^{\leq}_{i}}x_{i'j};$ $ i \in S_1$, $j \in S_2$

where $ F^{\leq}_{j}(i)$ is the set of agents of $S_2$ that $i$ ranks at the same level or better than $j$ and $C^{\leq}_{i}$ is the set of $S_1$ that are at the same level or better than $i$.

My question is: is there a way to model the stability constraints with a number of constraints in the order $O(n_1)$ rather than $O(n_1 n_2)$? because $n_2$ is very big and we already have a number of columns in order of $O(n_1 n_2)$.

  • $\begingroup$ Are you interested specifically in this approach for solving this problem, or will you be happy with any algorithm? $\endgroup$ – Yuval Filmus Apr 19 '20 at 10:33
  • $\begingroup$ any algorithm for this special case can be helpful for me $\endgroup$ – Farah Mind Apr 19 '20 at 10:51
  • $\begingroup$ You are trying to find an algorithm to solve an "asymatic stable assignment"! $\endgroup$ – Max N Jan 20 at 12:24

Your Answer

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

Browse other questions tagged or ask your own question.