pipette
ESEspañol

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

Shuichi Miyazaki, Suguru Tamaki

PreprintClaims a big step

In the authors' words

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

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 13 pages