← All Problems
Open

Stable Marriage Minimum Regret (SMMR)

Category: Matching
Tags:
CC

Input

A set of $n$ men and a set of $n$ women, for each person a ranking of the opposite sex according to their preference for a marriage partner, and an integer $k$, $1 \leq k \leq n$.

Problem

Is there a stable marriage in which every person has regret at most $k$?

Definitions

The regret of a person in a stable marriage is the position of her mate on her preference list.

Status

Open (Mayr and Subramanian [1], Subramanian [2]).

Remarks

This problem is in $\CC$, that is, it is equivalent to CCVP. The goal in this problem is to minimize the maximum regret of any person.

References

  1. E. W. Mayr and A. Subramanian (1992). The complexity of circuit value and network stability.
  2. A. Subramanian (1989). A new approach to stable matching problems.
  3. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.8.6.