Stable matching with uncertain linear preferences
From MaRDI portal
Publication:2309477
DOI10.1007/s00453-019-00650-0zbMath1435.91123arXiv1607.02917WikidataQ90667602 ScholiaQ90667602MaRDI QIDQ2309477
Ronald de Haan, Péter Biró, Nicholas Mattei, Serge Gaspers, Haris Aziz, Baharak Rastegari
Publication date: 1 April 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.02917
stable matchings; stable marriage problem; polynomial-time algorithms; NP-hard problems; uncertain preferences
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
91B68: Matching models
Related Items
Review of the theory of stable matchings and contract systems, Stable matching with multilayer approval preferences: approvals can be harder than strict preferences, Assignment mechanisms: common preferences and information acquisition, Stable matching with uncertain pairwise preferences
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matching markets under (in)complete information
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Stable marriage and indifference
- On the evaluation of election outcomes under uncertainty
- Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity
- The Potts model and the Tutte polynomial
- Stable Matching with Uncertain Linear Preferences
- Improved approximation results for the stable marriage problem
- Algorithmics of Matching Under Preferences
- College Admissions and the Stability of Marriage