Search Results

Documents authored by Cseh, Ágnes

Document
DOI: 10.4230/LIPIcs.CP.2022.16
Computing Relaxations for the Three-Dimensional Stable Matching Problem with Cyclic Preferences

Authors: Ágnes Cseh, Guillaume Escamocher, and Luis Quesada

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Constraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility. In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version.
Cite as

Ágnes Cseh, Guillaume Escamocher, and Luis Quesada. Computing Relaxations for the Three-Dimensional Stable Matching Problem with Cyclic Preferences. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cseh_et_al:LIPIcs.CP.2022.16,
  author =	{Cseh, \'{A}gnes and Escamocher, Guillaume and Quesada, Luis},
  title =	{{Computing Relaxations for the Three-Dimensional Stable Matching Problem with Cyclic Preferences}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.16},
  URN =		{urn:nbn:de:0030-drops-166450},
  doi =		{10.4230/LIPIcs.CP.2022.16},
  annote =	{Keywords: Three-dimensional stable matching with cyclic preferences, 3dsm-cyc, Constraint Programming, relaxation, almost stable matching}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.22
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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.21
Pairwise Preferences in the Stable Marriage Problem

Authors: Ágnes Cseh and Attila Juhos

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability - weak, strong and super-stability - under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.
Cite as

Ágnes Cseh and Attila Juhos. Pairwise Preferences in the Stable Marriage Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cseh_et_al:LIPIcs.STACS.2019.21,
  author =	{Cseh, \'{A}gnes and Juhos, Attila},
  title =	{{Pairwise Preferences in the Stable Marriage Problem}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.21},
  URN =		{urn:nbn:de:0030-drops-102603},
  doi =		{10.4230/LIPIcs.STACS.2019.21},
  annote =	{Keywords: stable marriage, intransitivity, acyclic preferences, poset, weakly stable matching, strongly stable matching, super stable matching}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.17
Popular Matchings in Complete Graphs

Authors: Ágnes Cseh and Telikepalli Kavitha

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Our input is a complete graph G = (V,E) on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is "globally stable" or popular. A matching M is popular if M does not lose a head-to-head election against any matching M': here each vertex casts a vote for the matching in {M,M'} where it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show here.
Cite as

Ágnes Cseh and Telikepalli Kavitha. Popular Matchings in Complete Graphs. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cseh_et_al:LIPIcs.FSTTCS.2018.17,
  author =	{Cseh, \'{A}gnes and Kavitha, Telikepalli},
  title =	{{Popular Matchings in Complete Graphs}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.17},
  URN =		{urn:nbn:de:0030-drops-99164},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.17},
  annote =	{Keywords: popular matching, complete graph, complexity, linear programming}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact