# Almost Stable Marriage Problem (Stable Matching Problem)

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 |