License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.71
URN: urn:nbn:de:0030-drops-155047
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15504/
Go to the corresponding LIPIcs Volume Portal

Yokoi, Yu

An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints

pdf-format:
LIPIcs-ISAAC-2021-71.pdf (0.8 MB)

Abstract

We present a polynomial-time 3/2-approximation algorithm for the problem of finding a maximum-cardinality stable matching in a many-to-many matching model with ties and laminar constraints on both sides. We formulate our problem using a bipartite multigraph whose vertices are called workers and firms, and edges are called contracts. Our algorithm is described as the computation of a stable matching in an auxiliary instance, in which each contract is replaced with three of its copies and all agents have strict preferences on the copied contracts. The construction of this auxiliary instance is symmetric for the two sides, which facilitates a simple symmetric analysis. We use the notion of matroid-kernel for computation in the auxiliary instance and exploit the base-orderability of laminar matroids to show the approximation ratio.
In a special case in which each worker is assigned at most one contract and each firm has a strict preference, our algorithm defines a 3/2-approximation mechanism that is strategy-proof for workers.

BibTeX - Entry

@InProceedings{yokoi:LIPIcs.ISAAC.2021.71,
  author =	{Yokoi, Yu},
  title =	{{An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{71:1--71:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15504},
  URN =		{urn:nbn:de:0030-drops-155047},
  doi =		{10.4230/LIPIcs.ISAAC.2021.71},
  annote =	{Keywords: Stable matching, Approximation algorithm, Matroid, Strategy-proofness}
}

Keywords: Stable matching, Approximation algorithm, Matroid, Strategy-proofness
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI