A sublinear parallel algorithm for stable matching

DOI10.1016/S0304-3975(99)00125-5zbMath0961.90088OpenAlexW2066306418WikidataQ126382620 ScholiaQ126382620MaRDI QIDQ1575960

Tomás Feder, Nimrod Megiddo, Serge A. Plotkin

Publication date: 23 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00125-5

zbMATH Keywords

linear programmingparallel algorithmstable matchingnonexpansive circuitsprimal-dual interior path-following method

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10)

Related Items (2)

Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ Local Matching Dynamics in Social Networks

Cites Work

• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• The complexity of circuit value and network stability
• Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
• A New Approach to Stable Matching Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: A sublinear parallel algorithm for stable matching