## 1 Introduction
After Algorithm GS finishes, the engaged pairs make up the output matching \(M\) (we may imagine that this time all the engaged pairs get married). **Theorem 1** ([PERSON] and [PERSON] [3]): _Algorithm GS always ends in a stable matching \(M\). This algorithm runs in \(O(|E|)\) time._  
An interesting problem, motivated by applications, is to find a stable matching of maximum size. As the applications of this problem are important (see e.g., in [5, 6], where detailed lists of known and possible applications are given that motivate investigating refined approximations), researchers started to develop good approximation algorithms in the past six years. We say that an algorithm is \(r\)-approximating, if it gives a stable matching \(M\) with size \(|M|\geq(1/r)\cdot|M_{\mathrm{opt}}|\), where \(M_{\mathrm{opt}}\) is a stable matching of maximum size. Observe that after a run of GS no unmarried man and unmarried woman can form an acceptable pair. Consequently Algorithm GS gives a \(2\)-approximation, and for complete bipartite graphs (every woman-man pair is acceptable), it gives the optimum. The first non-trivial approximation algorithm was given by [PERSON] _et al_. [7], where they gave a \(13/7\)-approximation if all ties are of length two. The breakthrough was achieved by [PERSON], [PERSON] and [PERSON] [8], who gave a \(15/8\)-approximation (for any length of ties). This was later improved by [PERSON] and [PERSON] [5] to a \(5/3\)-approximation for the special case, where ties are allowed on one side only, and moreover only at the ends of the lists. Their algorithm also applies to the Hospitals/Residents problem (see below) if residents have strictly ordered lists. If, moreover, ties are of size \(2\), [PERSON] _et al_. [7] gave an \(8/5\)-approximation and in [9] they described a randomized algorithm for this special case with expected ratio of \(10/7\). This problem is known to be NP-hard for even very restricted cases [10, 11]. Moreover, it is APX-hard [12] and, supposing P \(\
eq\) NP, it cannot be approximated within a factor of strictly less than \(21/19\), even if ties occur in the preference lists on one side only, furthermore, if every list is either totally ordered or consists of a single tied pair [7]. Moreover, refining the ideas of [7], [PERSON] [13] proved that an approximation within a factor of \(4/3-\varepsilon\) implies \((2-\varepsilon^{\prime})\)-approximation of vertex cover, and this result also applies to the case when each tie has length two. If, moreover, ties occur only in the preference lists on one side only, it was proved in [7] that an approximation within a factor of \(5/4-\varepsilon\) has the same implication. We note that interestingly the minimization version (where we are looking for a stable matching of minimum size) is also APX-hard [12]. We proposed a simple linear time \(5/3\)-approximating algorithm (called GSA2) for the general case of this problem, first presented at the first MATCH-UP workshop (see in [4, 14, 15]), and at the same time, an even simpler \(3/2\)-approximation (called GSA1) was given for the special case where ties are allowed on one side only. For this algorithm, the proof was also very short, see Section 2. This is also valid for the practically important \"Hospitals/Residents\" problem, where the lists of the residents are strict, see Section 5. During the talks given at the first MATCH-UP workshop in Reykjavik and at ESA in Karlsruhe, we posed several questions, conjectures and open problems. Many of them were answered in the meanwhile. The conjecture stating that the performance ratio proved for GSA2 is sharp proved to be true by [PERSON] [16], who gave a simple example where GSA2 really gives a matching of size exactly \(\frac{3}{5}\cdot|M_{\mathrm{opt}}|\). [PERSON] and [PERSON] [17] implemented a basic version of our algorithm for the one-sided-ties Hospitals/Residents problem and gave a detailed comparison with their best heuristic (which is not a local algorithm, and it needs some max-flow computation on an auxiliary graph).