Faster and simpler approximation of stable matchings (Q1736612)

Summary: We give a \(\frac{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(n^{3 / 2} m)\) time, where \(n\) denotes the number of people and \(m\) 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 stablemany-to-many matchings.