KFU. Card publication. A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

A COUNTEREXAMPLE OF SIZE 20 FOR THE PROBLEM OF FINDING A 3-DIMENSIONAL STABLE MATCHING WITH CYCLIC PREFERENCES

Form of presentation

Articles in international journals and collections

Year of publication

2023

��

��

Authors, employees of KFU

Lerner Eduard Yulevich, author

Bibliographic description in the original language

Lerner E.Yu. A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences / E.Yu. Lerner // Discrete Applied Mathematics - 2023. - Volume 333, 15 July. - Pages 1-12.

Annotation

As is known, the problem of finding a three-dimensional stable matching with cyclic preferences (3DSM-CYC) always has a solution, if the number of objects of each type (i.e., the problem size n) does not exceed 5. According to the conjecture proposed by Eriksson et al. (2006), this is true for any n. However, Lam and Plaxton (2019) have proposed an algorithm for constructing preference lists in 3DSM-CYC which has allowed them to disprove the mentioned conjecture. The size of the initially constructed counterexample equals 90; however, according to the results obtained by us recently for the problem with incomplete preference lists, one can use the same construction for getting a counterexample of size 45. The main contribution of this paper consists of reducing the size of the counterexample to n=20. We summarize results of the application of the technique developed by us for constructing counterexamples for 3DSM-CYC. In the final section of the paper we discuss a new variant of 3DSM, whose solution always exists and can be found within the same time as that required for solving 2DSM.

Keywords

3-dimensional stable matching, cyclic preferences, preference graph, Gale-Shapley algorithm

The name of the journal

Discrete Applied Mathematics

On-line resource for training course

http://dspace.kpfu.ru/xmlui/bitstream/handle/net/175939/F_3DSM_20_rev2.pdf?sequence=1&isAllowed=y

URL

https://doi.org/10.1016/j.dam.2023.02.020

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=280344&p_lang=2

Resource files

File name	Size (MB)	Format
F_3DSM_20_rev2.pdf	0,35	pdf	show / download

Full metadata record

Field DC	Value	Language
dc.contributor.author	Lerner Eduard Yulevich	ru_RU
dc.date.accessioned	2023-01-01T00:00:00Z	ru_RU
dc.date.available	2023-01-01T00:00:00Z	ru_RU
dc.date.issued	2023	ru_RU
dc.identifier.citation	Lerner E.Yu. A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences / E.Yu. Lerner // Discrete Applied Mathematics - 2023. - Volume 333, 15 July. - Pages 1-12.	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=280344&p_lang=2	ru_RU
dc.description.abstract	Discrete Applied Mathematics	ru_RU
dc.description.abstract	As is known, the problem of finding a three-dimensional stable matching with cyclic preferences (3DSM-CYC) always has a solution, if the number of objects of each type (i.e., the problem size n) does not exceed 5. According to the conjecture proposed by Eriksson et al. (2006), this is true for any n. However, Lam and Plaxton (2019) have proposed an algorithm for constructing preference lists in 3DSM-CYC which has allowed them to disprove the mentioned conjecture. The size of the initially constructed counterexample equals 90; however, according to the results obtained by us recently for the problem with incomplete preference lists, one can use the same construction for getting a counterexample of size 45. The main contribution of this paper consists of reducing the size of the counterexample to n=20. We summarize results of the application of the technique developed by us for constructing counterexamples for 3DSM-CYC. In the final section of the paper we discuss a new variant of 3DSM, whose solution always exists and can be found within the same time as that required for solving 2DSM.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	3-dimensional stable matching	ru_RU
dc.subject	cyclic preferences	ru_RU
dc.subject	preference graph	ru_RU
dc.subject	Gale-Shapley algorithm	ru_RU
dc.title	A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences	ru_RU
dc.type	Articles in international journals and collections	ru_RU