Papers for

matching platform developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Stable marriage matching algorithm runs in single-exponential time

A Single-Exponential Time Algorithm for the Maximum-Cardinality Weakly Stable Matching Problem with Ties and Incomplete Lists

Abstract: We study Stable Marriage with Ties and Incomplete lists (SMTI) under weak stability. For an instance with $n$ agents on each side, we give an exact algorithm that returns a maximum-cardinality weakly stable matching in $O^*(22.74^n)$ time. To the best of our knowledge, this is the first exact algorithm for this problem running in single-exponential time.

Thu 29 OctData Structures and Algorithms

The gist

This work addresses the problem of matching two groups of people, like men and women, where not everyone lists all possible partners and where ties in preferences may occur. The researchers developed an exact algorithm to find the largest set of matches that are stable under weak stability rules, meaning no pair wants to deviate given the ties. Importantly, their method runs in single-exponential time, which improves the efficiency over previous approaches for this problem.

Open → 2610.39764v1