1 Search Results for "Genç, Begüm"


Document
A Collection of Constraint Programming Models for the Three-Dimensional Stable Matching Problem with Cyclic Preferences

Authors: Ágnes Cseh, Guillaume Escamocher, Begüm Genç, and Luis Quesada

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)


Abstract
We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with. Our experiments not only led us to discover dependencies between the type of stability and the instance generation method, but also brought light to the role that learning and restarts can play in solving this kind of problems.

Cite as

Ágnes Cseh, Guillaume Escamocher, Begüm Genç, and Luis Quesada. A Collection of Constraint Programming Models for the Three-Dimensional Stable Matching Problem with Cyclic Preferences. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{cseh_et_al:LIPIcs.CP.2021.22,
  author =	{Cseh, \'{A}gnes and Escamocher, Guillaume and Gen\c{c}, Beg\"{u}m and Quesada, Luis},
  title =	{{A Collection of Constraint Programming Models for the Three-Dimensional Stable Matching Problem with Cyclic Preferences}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.22},
  URN =		{urn:nbn:de:0030-drops-153137},
  doi =		{10.4230/LIPIcs.CP.2021.22},
  annote =	{Keywords: Three-dimensional stable matching with cyclic preferences, 3DSM-cyc, Constraint Programming, fairness}
}
  • Refine by Author
  • 1 Cseh, Ágnes
  • 1 Escamocher, Guillaume
  • 1 Genç, Begüm
  • 1 Quesada, Luis

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 3DSM-cyc
  • 1 Constraint Programming
  • 1 Three-dimensional stable matching with cyclic preferences
  • 1 fairness

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail