Reproduce “An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Yu Yokoi

Yu Yokoi's research presents a polynomial-time algorithm for finding a maximum-cardinality stable matching in complex many-to-many settings that include both ties in preferences and hierarchical laminar constraints. The proposed method achieves a 3/2-approximation ratio by transforming the original problem into an auxiliary instance solvable via base-orderable matroids.

Key insights

  • Complex stable matching problems with ties and laminar constraints can be effectively modeled and approximately solved using transformations into auxiliary instances that leverage base-orderable matroids.
  • A novel structural lemma (Lemma 5) provides a generalized property for the intersection of base-orderable matroids, crucial for proving the approximation guarantee.
  • The symmetric triplication of contracts and careful ordering of preferences allow for a static analysis of the approximation ratio, generalizing techniques from simpler tie-aware stable matching algorithms.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.