greater than 33/29 unless P=NP [6]. A 3/2-approximation algorithm has been proposed in [7].

## 2 Background 2.1 Stable Marriage Problems With Ties And Incompleteness

A stable marriage (SM) problem [1] consists of matching members of two different sets, usually called men and women. When there are n men and n women, the SM problem is said to have size n. Each person strictly ranks all members of the opposite sex. The goal is to match the men with the women so that there are no two people of opposite sex who would both rather marry each other than their current partners. Such a marriage is called stable. At least one stable marriage exists for every SM problem. In fact, the set of stable marriages forms a lattice. Gale and Shapley give a polynomial time algorithm to find the stable marriage at the top (or bottom) of this lattice [2].

In this paper we consider a variant of the SM problem where preference lists may include ties and may be incomplete. This variant is denoted by SMTI [8]. Ties express indifference in the preference ordering, while incompleteness models unacceptability for certain partners. Definition 1 (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 are acceptable for 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 2 (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.

An example of a SMTI problem with four men and women is shown in Table 1. A SMTI problem is described by giving, for each man and woman, the corresponding preference list over members of the other sex. For example, by writing 2 : 2 (3 4) among the men's preference lists we mean that man m2 strictly prefers woman w2 to women w3 and w4, that are equally preferred.

| men's preference lists women's preference lists 1: 2 1 1: 3 1 (2 4) 2: 2 (3 4) 2: 1 4 2 3: (1 2 3 4) 3: (1 2) (4 3) 4: (3 2) 1 4 4: (3 2 4)   |
|-----------------------------------------------------------------------------------------------------------------------------------------------|

Table 1. An example of a SMTI problem of size 4.

Definition 3 (Blocking pairs in SMTIs). 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