Research My IBM Log in
Conference paper

Sublinear parallel algorithm for stable matching

Abstract

Parallel algorithms for various versions of the stable matching problem are presented. The algorithms are based on the primal-dual interior path-following method for linear programming. The main result is that a stable matching can be found in O*(√m) time by a polynomial number of processors, where m is the total length of preference lists of individuals.

Semiconductors Artificial Intelligence Quantum Computing Hybrid Cloud About Publications Blog Events Careers Contact Research Topics People Projects Newsletter X LinkedIn YouTube RSS Contact IBM Privacy Terms of use Accessibility