Approximating stable matchings with ties of bounded size

DOI10.1007/978-3-030-57980-7_12MaRDI QIDQ2109960zbMATH OpenOpenAlexFDO

Authors Jochen Könemann, Kanstantsin Pashkovich, Natig Tofigzade

Publication date 21 December 2022

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsstable matching

Mathematics Subject Classification ID

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

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.

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

Cited in

(10)

• The Complexity of Approximately Counting Stable Matchings
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• On the approximability of the stable matching problem with ties of size two
• A simply exponential upper bound on the maximum number of stable matchings
• Maximum stable matching with one-sided ties of bounded length
• Maximum stable matching with one-sided ties of bounded length
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• Parameterized algorithms for stable matching with ties and incomplete lists
• Many-to-many stable matchings with ties in trees
• Stable fractional matchings

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)