## 1 Introduction  
In the paper, we consider a variant of the problem called **Stable Matchings**, known also in the literature as the **Stable Marriage** problem. The problem is defined as follows. We are given two sets \(W\) and \(U\) of women and men. Each woman \(w\) of \(W\) has a preference list \(L_{w}\) of a subset of men, and similarly, each man \(m\) of \(U\) has a preference list \(L_{m}\) of a subset of women. The preference lists are linearly ordered lists of **ties**, which are subsets of men (or respectively, women), who are equally good for a given woman (respectively, man). Ties are disjoint and can contain also one person, appropriately a man or a woman. Thus if \(m\) and \(m^{\prime}\) are on list \(L_{w}\) of woman \(w\), then either (1) \(w\) prefers \(m\) to \(m^{\prime}\), or in other words, \(m\) is better for \(w\) than \(m^{\prime}\); or (2) \(m\) and \(m^{\prime}\) are in a tie on \(L_{w}\), and then we say that \(w\) is indifferent between \(m\) and \(m^{\prime}\) or that \(m\) and \(m^{\prime}\) are equally good for her; or (3) \(w\) prefers \(m^{\prime}\) to \(m\). Man \(m\) and woman \(w\) are said to be **mutually acceptable** to each other if they belong to each other's preference lists. The most preferred person(s) is (are) at the top of the preference lists. A **matching** is a set of pairs \((m,w)\) such that \(m\in U,w\in W\) and \(m\) and \(w\) are mutually acceptable, and each man/woman belongs to at most one pair. If \((m,w)\) belongs to a certain matching \(M\), then we write \(M(m)=w\), which means that in \(M\) woman \(w\) is a partner of \(m\), and analogously that \(M(w)=m\). If man \(m\) (or woman \(w\)) is not contained in any pair of a matching \(M\), then we say that \(m\) (or \(w\)) is **unmatched** or **free** in \(M\). A matching \(M\) is called **stable** if it does not admit a **blocking pair**. A pair \((m,w)\) is blocking for \(M\) if (1) \(m\) and \(w\) are mutually acceptable; (2) \(m\) is unmatched or prefers \(w\) to \(M(m)\); and (3) \(w\) is unmatched or prefers \(m\) to \(M(w)\). Each instance of the problem can be represented by a bipartite graph \(G=(U\cup W,E)\) with vertices of \(U\) representing men, vertices of \(W\) representing women and edges \(E\) connecting all mutually acceptable pairs of men and women. The problem we are interested in is that of finding a stable matching that has the largest cardinality. The version in which there are no ties in the preference lists of men and women has been long known and an algorithm by [PERSON] (1980) solves it exactly in \(O(m)\) time, where \(m\) denotes the number of edges in the underlying graph. In the version without ties a stable matching always exists, and every stable matching has the same cardinality. If we allow ties, as in the problem we consider in this paper, then a stable matching also always exists and can be found via the Gale-Shapley algorithm by breaking ties arbitrarily. However, the sizes of stable matchings can vary considerably, and the problem of finding a stable matching of maximum cardinality is \(NP\)-hard, which was shown by [PERSON] _et al._ in [PERSON] et al. (2014). Therefore it is desirable to devise an approximation algorithm for the problem. **Previous and related results** Previous approximation algorithms were presented in [PERSON] (1996); [PERSON] (1997); [PERSON] (1998); [PERSON] et al. (2014). Currently the best approximation algorithm is by [PERSON] (1996) and achieves the approximation guarantee \(\frac{3}{2}\). Its running time is \(O(n^{3/2}m)\), where \(n\) denotes the number of vertices and \(m\) the number of edges. Inapproximabilty results were shown in [PERSON] (1996); [PERSON] and [PERSON] (1998); [PERSON] and [PERSON] (1999). For a variant of the Stable Matchings problem, in which ties are allowed on one side only, an approximation algorithm achieving the ratio \(\frac{25}{17}\) has been given in [PERSON] and [PERSON] (1998).