A matroid generalization of the super-stable matching problem

DOI10.1137/21M1437214MaRDI QIDQ5084102zbMATH OpenFDO

Authors Naoyuki Kamiyama

Publication date 23 June 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.03820

zbMATH Keywords

matroidstable matchingsuper-stability

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matching models (91B68)

Abstract: A super-stable matching, which was introduced by Irving, is a solution concept in a variant of the stable matching problem in which the preferences may contain ties. Irving proposed a polynomial-time algorithm for the problem of finding a super-stable matching if a super-stable matching exists. In this paper, we consider a matroid generalization of a super-stable matching. We call our generalization of a super-stable matching a super-stable common independent set. This can be considered as a generalization of the matroid generalization of a stable matching for strict preferences proposed by Fleiner. We propose a polynomial-time algorithm for the problem of finding a super-stable common independent set if a super-stable common independent set exists.

Recommendations

• Stable matchings with ties, master preference lists, and matroid constraints
• scientific article; zbMATH DE number 1757951
• The Stable Roommates Problem with Ties
• Super-stability in the student-project allocation problem with ties
• Pareto stable matchings under one-sided matroid constraints

Cites work

• A Fixed-Point Approach to Stable Matchings and Some Applications
• A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas
• A matroid approach to stable matchings with lower quotas
• A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An algorithm for strong stability in the student-project allocation problem with ties
• College Admissions and the Stability of Marriage
• Designing matching mechanisms under constraints: an approach from discrete convex analysis
• Finding a stable allocation in polymatroid intersection
• scientific article; zbMATH DE number 1617265 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• On the Lattice Structure of Stable Allocations in a Two-Sided Discrete-Concave Market
• Stable marriage and indifference
• Stable matchings with ties, master preference lists, and matroid constraints
• The stable marriage problem with master preference lists

Cited in

(5)

• Stable matchings with ties, master preference lists, and matroid constraints
• Strongly stable matchings under matroid constraints
• Super-stable common independent sets of generalized matroids
• Modifying an instance of the super-stable matching problem
• Characterization of super-stable matchings

This page was built for publication: A matroid generalization of the super-stable matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084102)