A (2-c log N/N)–Approximation Algorithm for the Stable Marriage Problem

’Algorithm Theory - SWAT 2004’ 9th Scandinavian Workshop on Algorithm Theory, Humlebæk, Denmark, July 8-10, 2004. ProceedingsWe propose an approximation algorithm for the problem of finding a maximum stable matching when both ties and unacceptable partners are allowed in preference lists. Our algorithm achieves the approximation ratio (2-c log N/N) for an arbitrarily positive constant c, where N denotes the number of men in an input. This improves the trivial approximation ratio of two