Approximating stable matchings with ties of bounded size

DOI10.1007/978-3-030-57980-7_12zbMATH Open1506.91118arXiv2005.05228OpenAlexW3089746070MaRDI QIDQ2109960FDOQ2109960

Authors: Jochen Könemann, Kanstantsin Pashkovich, Natig Tofigzade 

Publication date: 21 December 2022

Abstract: Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete preferences, computing a stable matching of maximum cardinality is known to be NP-hard. In this paper we present a $(3L-2)/(2L-1)$-approximation algorithm for the stable matching problem with ties of size at most $L$ and incomplete lists. Our result matches the known lower bound on the integrality gap for the associated LP formulation.

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

Recommendations

• Improved approximation of the stable marriage problem
• On the approximability of the stable matching problem with ties of size two
• Algorithms and Computation
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• Improved approximation results for the stable marriage problem

zbMATH Keywords

combinatorial optimizationapproximation algorithmsstable matching

Mathematics Subject Classification ID

Approximation algorithms (68W25) Matching models (91B68) Algorithmic game theory and complexity (91A68)

Cited In (5)

• The Complexity of Approximately Counting Stable Matchings
• A simply exponential upper bound on the maximum number of stable matchings
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• Parameterized algorithms for stable matching with ties and incomplete lists

This page was built for publication: Approximating stable matchings with ties of bounded size

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