We present new integer linear programming (ILP) models for NP-hard optimisation problems in instances of the Stable Marriage problem with Ties and Incomplete lists (SMTI) and its many-to-one generalisation, the Hospitals Residents problem with Ties (HRT). These models can be used to efficiently solve these optimisation problems when applied to (i) instances derived from real-world applications, and (ii) larger instances that are randomly-generated. In the case of SMTI, we consider instances arising from the pairing of children with adoptive families, where preferences are obtained from a quality measure of each possible pairing of child to family. In this case we seek a maximum weight stable matching. We present new algorithms for preprocessing instances of SMTI with ties on both sides, as well as new ILP models. Algorithms based on existing state-of-the-art models only solve 6 of our 22 real-world instances within an hour per instance, and our new models solve all 22 instances within a mean runtime of 60 seconds. For HRT, we consider instances derived from the problem of assigning junior doctors to foundation posts in Scottish hospitals. Here we seek a maximum size stable matching. We show how to extend our models for SMTI to the HRT case. For the real instances, we reduce the mean runtime from an average of 144 seconds when using state-of-the-art methods, to 3 seconds when using our new ILP-based algorithms. We also show that our models outperform considerably state-of-the-art models on larger randomly-generated instances of SMTI and HRT.
@cite_22: In an instance of the stable marriage problem with ties and incomplete preference lists, stable matchings can have different sizes. It is APX-hard to compute a maximum cardinality stable matching, but there have recently been proposed polynomial-time approximation algorithms, with constant performance guarantees for both the general version of this problem, and for several special cases. Our contribution is to describe a @math -approximation algorithm for the general version of this problem, improving upon the recent @math -approximation algorithm of Kiraly. Interest in such algorithms arises because of the problem's application to centralized matching schemes, the best known of which involve the assignment of graduating medical students to hospitals in various countries.
@cite_15: A velocity error compensator is provided for use in a time base corrector of the type having a memory into which successive samples of a periodic information signal, such as a video signal, are written at a write-in rate that is synchronized with time base errors in the information signal, such that plural periods, such as plural lines, of the information signal are stored in the memory, and from which the successive samples are read at a constant read-out rate. The velocity error compensator comprises a velocity error detector for detecting velocity errors in successive periods, or lines, of the information signal written into the memory; and a sample level compensator for compensating the level of a sample read out from the memory as a function of the detected velocity error, such that the level of the read out sample is modified to be equal to the level that the read out sample should have had at the time it was read out if there had been no velocity error.
@cite_0: The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2 (1 p L−2) for instances in which only men have ties of length at most L. When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13 7( 1.1052).
@cite_24: We consider a two-sided market under incomplete preference lists with ties, where the goal is to find a maximum size stable matching. The problem is APX-hard, and a 3 2-approximation was given by McDermid [1]. This algorithm has a non-linear running time, and, more importantly needs global knowledge of all preference lists. We present a very natural, economically reasonable, local, linear time algorithm with the same ratio, using some ideas of Paluch [2]. In this algorithm every person make decisions using only their own list, and some information asked from members of these lists (as in the case of the famous algorithm of Gale and Shapley). Some consequences to the Hospitals Residents problem are also discussed.
@cite_31: We give a 3 2 -approximation algorithm for finding stable matchings that runs in O(m) time. The previous most well-known algorithm, by McDermid, has the same approximation ratio but runs in O(n3 2m) time, where n denotes the number of people andm is the total length of the preference lists in a given instance. In addition, the algorithm and the analysis are much simpler. We also give the extension of the algorithm for computing stable many-to-many matchings.
MAX-SMTI is also not approximable within a factor of 21 19 @cite_0 unless @math , even if preferences on one side are strictly ordered, and on the other side are either strictly ordered or a tie of length two. The best currently-known performance guarantee is 3 2, achieved first in non-linear running time @cite_22 and later improved to linear time @cite_24 @cite_31 , although better guarantees can be achieved in certain restrictions @cite_15 . Kir 'aly @cite_24 shows how to extend his 3 2-approximation algorithm for MAX-SMTI to HRT.