

![0_image_0.png](0_image_0.png)

at each step, these are easily identifiable, and they form reversible moves that connect the state space and converge to the uniform distribution. Unfortunately, Bhatnagar et al. show that this random walk has an exponential convergence time, which would appear to suggest that the approach may not be feasible in practice.

In this paper we also consider a variant of the SM problem where preference lists may include ties and may be incomplete. This variant is denoted by SMTI [10]. Ties express indifference in the preference ordering, while incompleteness models unacceptability only for certain partners. Finally, our empirical data support the theoretical results in [14] about parameterized complexity of the stable marriage problem.

Definition 5 (SMTI marriage) Given a SMTI problem with n men and n *women, a* marriage M *is a one-to-one matching between men and women such that partners accept* each other. If a man m and a woman w are matched in M*, we write* M(m) = w and M(w) = m. If a person p is not matched in M *we say that he/she is single.* Definition 6 (Marriage size) Given a SMTI problem of size n and a marriage M*, its* size is the number of men (or women) that are married. Definition 7 (Blocking pairs in SMTI problems) Consider a SMTI problem P, a marriage M for P, a man m and a woman w*. A pair* (m, w) *is a blocking pair in* M iff m and w accept each other and m is either single in M *or he strictly prefers* w to M(m),
and w is either single in M *or she strictly prefers* m to M(w).

Definition 8 (Weakly Stable Marriages) Given a SMTI problem P, a marriage M for P *is weakly stable iff it has no blocking pairs.*
As we will consider only weakly stable marriages, we will simply call them stable marriages. Given a SMTI problem, there may be several stable marriages of different size. If the size of a marriage coincides with the size of the problem, it is said to be a perfect matching. Solving a SMTI problem means finding a stable marriage with maximal size. This problem is NP-hard [12].

## 2.2 Local Search

Local search [8] is one of the fundamental paradigms for solving computationally hard combinatorial problems. Local search methods in many cases represent the only feasible