EUVIMEDEUVIMED entdecken
Crossref

Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching

Frederik Glitzner, David Manlove

ACM Transactions on Economics and Computation · 02.05.2026

DOI: 10.1145/3814616 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 02.05.2026. Verfasst von Frederik Glitzner und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 47 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the Stable Fixtures problem, a many-to-many generalisation of the classical non-bipartite Stable Roommates matching problem. Building on the foundational work of Tan on stable partitions, we extend his results to this significantly more general setting and develop a rich framework for understanding stable structures. Our main contribution, the notion of a generalised stable partition (GSP) , not only characterises the solution space but also serves as a versatile tool for ordinal preference systems with capacity constraints. We show that a GSP can be computed efficiently and can provide an elegant representation of key aspects of a preference system. Leveraging a connection to stable half-matchings, we also establish an analogous Rural Hospitals Theorem for stable half-matchings and GSPs, and connect our results to recent work on near-feasible matchings, providing a simpler algorithm and tighter analysis. Our work also addresses the computational challenges of finding optimal stable half-matchings and GSPs, presenting a flexible integer linear programming model for various objectives. Beyond theoretical insights, we conduct the first empirical analysis of random Stable Fixtures instances. Our work unifies and extends classical and recent perspectives on stability in non-bipartite stable matching and establishes new tools and techniques for stable matchings and their applications.

Zitieren

APA

Glitzner, F., & Manlove, D. (2026). Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching. ACM Transactions on Economics and Computation. https://doi.org/10.1145/3814616

Vancouver

Glitzner F, Manlove D. Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching. ACM Transactions on Economics and Computation. 2026. doi:10.1145/3814616

BibTeX
@article{Glitzner2026,
  author = {Glitzner, Frederik and Manlove, David},
  title = {Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching},
  journal = {ACM Transactions on Economics and Computation},
  year = {2026},
  doi = {10.1145/3814616}
}
Kostenlos starten →