Cover Image

Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cheng, Christine T., Rosenbaum, Will
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computer Science and Game Theory Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Quadratic Lower Bound for Stable Roommates Solvability
by: Rosenbaum, Will
Published: (2025)

Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem
by: Glitzner, Frederik, et al.
Published: (2024)

Near-Feasible Stable Matchings: Incentives and Optimality
by: Glitzner, Frederik
Published: (2026)

Optimal Capacity Modification for Stable Matchings with Ties
by: Ranjan, Keshav, et al.
Published: (2024)

Stable Matching with Interviews
by: Ashlagi, Itai, et al.
Published: (2025)

Stable Matching with Deviators and Conformists
by: Glitzner, Frederik, et al.
Published: (2026)

Stable Hypergraph Matching in Unimodular Hypergraphs
by: Biró, Péter, et al.
Published: (2025)

A Minimax Perspective on Almost-Stable Matchings
by: Glitzner, Frederik, et al.
Published: (2026)

Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences
by: McCauley, Samuel, et al.
Published: (2026)

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
by: Glitzner, Frederik, et al.
Published: (2025)

Efficiency in the Roommates Problem
by: Kuwahara, Keita
Published: (2025)

Partitioned Matching Games for International Kidney Exchange
by: Benedek, Márton, et al.
Published: (2023)

A new approach to bipartite stable matching optimization
by: Fleiner, Tamás, et al.
Published: (2024)

The Popular Dimension of Matchings
by: Connor, Frank, et al.
Published: (2025)

PackIt! Gamified Rectangle Packing
by: Garrison, Thomas, et al.
Published: (2024)

Extending Stable and Popular Matching Algorithms from Bipartite to Arbitrary Instances
by: Csáji, Gergely
Published: (2024)

Control in Stable Marriage and Stable Roommates: Complexity and Algorithms
by: Chen, Jiehua, et al.
Published: (2025)

Condorcet Dimension and Pareto Optimality for Matchings and Beyond
by: Kavitha, Telikepalli, et al.
Published: (2026)

Optimal Competitive Ratio of Two-sided Online Bipartite Matching
by: Tang, Zhihao Gavin
Published: (2026)

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
by: Bei, Xiaohui, et al.
Published: (2025)

On the Parameterized Complexity of Controlling Amendment and Successive Winners
by: Yang, Yongjie
Published: (2025)

Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
by: Pashkovich, Kanstantsin, et al.
Published: (2026)

Parameterized Algorithms for Kidney Exchange
by: Maiti, Arnab, et al.
Published: (2021)

Robust Popular Matchings
by: Bullinger, Martin, et al.
Published: (2024)

The Secretary Problem with Predicted Additive Gap
by: Braun, Alexander, et al.
Published: (2024)

A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
by: Takazawa, Kenjiro
Published: (2024)

MATWA: A Web Toolkit for Matching under Preferences
by: Glitzner, Frederik, et al.
Published: (2024)

Matching with Nested and Bundled Pandora Boxes
by: Bowers, Robin, et al.
Published: (2024)

Edge-Weighted Online Bipartite Matching
by: Fahrbach, Matthew, et al.
Published: (2020)

Fairness and Efficiency in Online Class Matching
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2024)

Stationary Online Contention Resolution Schemes
by: Aminian, Mohammad Reza, et al.
Published: (2026)

Six Candidates Suffice to Win a Voter Majority
by: Charikar, Moses, et al.
Published: (2024)

Approximately Dominating Sets in Elections
by: Charikar, Moses, et al.
Published: (2025)

The Distortion of Prior-Independent b-Matching Mechanisms
by: Caragiannis, Ioannis, et al.
Published: (2026)

Fairness and Efficiency in Two-Sided Matching Markets
by: Jain, Pallavi, et al.
Published: (2025)

Online Matching Meets Sampling Without Replacement
by: Huang, Zhiyi, et al.
Published: (2024)

Prophet Secretary and Matching: the Significance of the Largest Item
by: Chen, Ziyun, et al.
Published: (2024)

Prophet Upper Bounds for Online Matching and Auctions
by: Soto, José, et al.
Published: (2024)

Truthful Matching with Online Items and Offline Agents
by: Feldman, Michal, et al.
Published: (2022)

Approximating Nash Social Welfare by Matching and Local Search
by: Garg, Jugal, et al.
Published: (2022)