## 2 Related Work
Other local search methods have been presented for SMTI instances, but in terms of parameterized complexity in the framework introduced by [24]. In SMTI instances, the parameter can be the number of ties, the maximum or the overall length of ties [25]. In [25], the authors investigate the applicability of a local search algorithm for the problem and they examine the possibilities for giving an FPTalgorithm or an FPT approximation algorithm for finding an egalitarian or a minimum regret stable matching. In general, few papers have investigated the connection of parameterized complexity and local search, although attention to this topic has been increasing recently [26]. In [27], the framework of parameterized complexity is used to deal with the hospitals/residents with couples problem, a variant of the classical stable marriage problem. This is the extension of the hospitals/residents problem, where residents are allowed to form pairs and submit joint rankings over hospitals. In this problem, the authors consider the number of couples as a parameter, apply a local search approach and examine the possibilities for giving FPT algorithms applicable in this context. In [6], [PERSON] and [PERSON] give an exhaustive empirical study of the stable marriage problem with ties and incomplete lists, using a constraint programming encoding of the problem. Then, the encoded problem can be solved using off the shelf CPtechnology. They present results for the decision problem \"Is there a stable matching of size \(n\)?\" and for the optimization problem of finding a maximum or minimum cardinality stable matching. In particular, regarding the optimization problem of finding the largest stable marriage, their complete method (based on the solution of the CP encoding of the problem using the Choco constraint programming toolkit [28]) finds stable marriages of a size of 9.3 (in average)considering problems of a size of 10 with no ties. When the amount of ties increases, the size increases, as well. Our local search approach obtains very similar results using a test set generated in the same way. [PERSON] and [PERSON] in [29] give a SATencoding of the stable marriage problem with ties and incomplete lists. Using such an encoding, they obtain very good results in the decision problem of whether there is a perfect matching. Even though in our experiments, we often find a perfect matching, we consider a different problem from the one solved in [29]. In [30], [PERSON] and [PERSON], propose a distributed approach to the stable marriage problem with ties and incomplete lists with the aim of keeping preference lists private for privacy reasons. They extend some specialized centralized algorithms (such as the Extended Gale Shapley algorithm) to the distributed case. Moreover, they provide a generic distributed constraint programming model. In their experimental evaluation, they consider the communication effort and the computational cost (in terms of constraint checks) which are not applicable to our centralized approach. However, they show also the maximum cardinality of the marriages found by their algorithms considering SMTI instances. Considering problems of the same size, the probability of ties and the incompleteness they used, we obtain marriages of very similar cardinality. In [31], [PERSON] and [PERSON] present two heuristic approaches to find the largest stable matching in the context of the hospital resident-oriented (HR) problems with incomplete lists and ties only in the hospitals' preference lists. One of the algorithms is based on the hospital-oriented version of the Gale-Shapley algorithm, and the other one is based on the resident version. Heuristics are used to decide how to break ties in order to maximize the size of the returned marriage. In fact, the ways in which ties are broken can significantly affect the size of the stable matching found, and in the extreme case, there may be two matchings differing in size by a factor of two [4].