Definition 10 (Undominated blocking pair) *A men- (resp., women-) undominated* blocking pair is a blocking pair such that there is no other blocking pair that dominates it from the men's (resp., women's) point of view.

It is easy to see that, if M is an unstable marriage, (m, w) an men- (resp., women-)
undominated blocking pair in M, m′ = M(w), w
′ = M(m), and M′is obtained from M by removing (m, w), there are no blocking pairs in M′in which m (resp., w) is involved. This property would not be true if we removed a dominated blocking pair. This is why we focus on the removal of undominated blocking pairs when we pass from one marriage to another in our local search algorithm.

Considering again the SM in Table 1 and the marriage 2 7 4 8 6 3 5 1. The blocking pair
(m8, w4) dominates (from the men's point of view) (m8, w2). If we remove (m8, w2) from the marriage, (m8, w4) will remain. On the other hand, removing (m8, w4) also eliminates
(m8, w2). Thus, removing (m8, w4) is more useful than removing (m8, w2).

By using the undominated blocking pairs instead of all the blocking pairs, we also limit the size of the neighborhood, since each man or woman is involved in at most one undominated blocking pair. Hence we have at most 2n neighbor marriages to evaluate.

Let us now analyse more carefully the set of blocking pairs considered by SML1. Consider the case in which a man miis in two blocking pairs, say (mi, wj ) and (mi, wk), and assume that (mi, wj ) dominates (mi, wk) from the men's point of view. Then, let wj be in another blocking pair, say (mz, wj ), that dominates (mi, wj ) from the women's point of view. In this situation, SML1 returns (mz, wj ) because it computes the undominated blocking pairs from men's point of view (which are (mi, wj ) and (mz, wj )) and, among those, maintain the undominated ones from the women's point of view ((mz, wj ) in this case). The removal of
(mz, wj ) automatically eliminates (mi, wj ) from the set of blocking pairs of the marriage, since it is dominated by (mz, wj ). However, the blocking pair (mi, wk) is still present because the blocking pair that dominated it (i.e. (mi, wj )) is not a blocking pair any longer. We also consider a procedure that will return in addition the blocking pair (mi, wk), so to avoid having to consider it again in the subsequent step of the local search algorithm. We call SML2 the algorithm obtained from SML1 by using this new way to compute the blocking pairs.

Since dominance between blocking pairs is defined from one gender's point of view, at the beginning of our algorithms we randomly choose a gender and, at each search step we change the role of the two genders. For example, in SML1, if we start by finding the undominated blocking pairs from the men's point of view and, among those, we keep only the undominated blocking pairs from the women's point of view, in the following second step we do the opposite, and so on. In this way we ensure that SML1 and SML2 are gender neutral.

Summarizing, we have defined three algorithms, called SML, SML1, and SML2, to find a stable marriage for a given SM instance. Such algorithms differ only for the set of blocking pairs considered to define the neighborhood.

## 4 Local Search For Smti Problems

To adapt the SML algorithm to solve problems with ties and incomplete lists it is important to recall that an SMTI may have several stable marriages of different size. Thus, solving an SMTI problem means finding a stable marriage with maximal size. If the size of the marriage coincide with the size of the problem, it is said to be perfect and the algorithm can stop before the step limit. Otherwise the algorithm returns the best marriage found during