新论文 · v1arXiv:2610.39764
A Single-Exponential Time Algorithm for the Maximum-Cardinality Weakly Stable Matching Problem with Ties and Incomplete Lists
Shuichi Miyazaki, Suguru Tamaki
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.
尚无 AI 解读，展示原文摘要
cs.DS