Almost Stable Marriage Problem (Stable Matching Problem)

From Algorithm Wiki
Revision as of 12:03, 15 February 2023 by Admin (talk | contribs)
Jump to navigation Jump to search

Description

The task in the Almost Stable Marriage Problem is to find a matching that minimises the number of unstable edges, but the matching does not have to be a maximum matching.

Related Problems

Generalizations: Stable Marriage Problem

Related: Stable Roommates Problem, Boolean d-Attribute Stable Matching, Stable Matching Verification, Stable Pair Checking

Parameters

n: number of men and number of women

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Valentin Polishchuk, and Jukka Suomela 2008 $O({1})$ $O({1})$ 2 + \epsilon Parallel Time