We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Faster and Simpler Approximation of Stable Matchings.
- Authors
Paluch, Katarzyna
- Abstract
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.
- Subjects
APPROXIMATION algorithms; COMPUTER algorithms; MATCHING theory; MARRIAGE theorem; GRAPH theory
- Publication
Algorithms, 2014, Vol 7, Issue 2, p189
- ISSN
1999-4893
- Publication type
Article
- DOI
10.3390/a7020189