КФУ. Карточка публикации. A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

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

Форма представления

Статьи в зарубежных журналах и сборниках

Год публикации

2023

Язык

английский

Авторы, сотрудники КФУ

Лернер Эдуард Юльевич, автор

Библиографическое описание на языке оригинала

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.

Аннотация

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.

Ключевые слова

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

Название журнала

Discrete Applied Mathematics

Ссылка для РПД

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

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

https://repository.kpfu.ru/?p_id=280344

Файлы ресурса

Название файла	Размер (Мб)	Формат
F_3DSM_20_rev2.pdf	0,35	pdf	посмотреть / скачать

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Лернер Эдуард Юльевич	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/?p_id=280344	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	Статьи в зарубежных журналах и сборниках	ru_RU