Literature by the same author
plus at Google Scholar

Bibliografische Daten exportieren
 

Computing relaxations for the three-dimensional stable matching problem with cyclic preferences

Title data

Cseh, Ágnes ; Escamocher, Guillaume ; Quesada, Luis:
Computing relaxations for the three-dimensional stable matching problem with cyclic preferences.
In: Constraints. Vol. 28 (2023) . - pp. 138-165.
ISSN 1572-9354
DOI: https://doi.org/10.1007/s10601-023-09346-3

Abstract in another language

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.

Further data

Item Type: Article in a journal
Refereed: Yes
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics > Chair Mathematical Economics - Univ.-Prof. Dr. Jörg Rambau
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data > Chair Dynamical Systems and Data - Univ.-Prof. Dr. Peter Koltai
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Date Deposited: 22 Jun 2023 07:21
Last Modified: 08 Aug 2023 12:54
URI: https://eref.uni-bayreuth.de/id/eprint/81382