KFU. Card publication. Контрпримеры малого размера для трехмерной задачи поиска устойчивых мэтчингов с циклическими предпочтениями

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

КОНТРПРИМЕРЫ МАЛОГО РАЗМЕРА ДЛЯ ТРЕХМЕРНОЙ ЗАДАЧИ ПОИСКА УСТОЙЧИВЫХ МЭТЧИНГОВ С ЦИКЛИЧЕСКИМИ ПРЕДПОЧТЕНИЯМИ

Form of presentation

Articles in Russian journals and collections

Year of publication

2022

Язык

русский

Authors, employees of KFU

Lerner Eduard Yulevich, author

Bibliographic description in the original language

Lerner E.Yu. Kontrprimery malogo razmera dlya trekhmernoy zadachi poiska ustoychivykh metchingov s ciklicheskimi predpochteniyami / E.Yu. Lerner // Izvestiya vysshikh uchebnykh zavedeniy. Matematika. - 2022. - № 6. - S. 26-36.

Annotation

Рассмотрим n мужчин, n женщин и n собак, каждый мужчина имеет полный список предпочтений женщин, каждая женщина полный список предпочтений собак и каждая собака имеет полный список предпочтений мужчин (мы рассматриваем так называемую 3D-CYC problem --- трехмерную задачу с циклическими предпочтениями). Трисочетание есть набор n непересекающихся троек, содержащих по одному представителю каждого гендера. Трисочетание называется устойчивым (так называемым stable matching (SM)), если не существует мужчины, женщины и собаки из разных троек предпочитающих друг друга партнерам в своих тройках. Гиптотеза Eriksson, Sostrand и Strimling (2006) состояла в том, что задача отыскания SM (так называемая 3DSM-CYC задача) всегда имеет решение. Постепенно гипотеза была доказана для всех n<6. Однако, Lam и Paxton (2019) предложили алгоритм конструирования матриц предпочтений для 3DSM-CYC размера n=90, при которых M не существует. Вопрос о существовании контрпримеров меньшего размера оставался открытым. В этой работе мы построим наглядный контрпример для 3DSM-CYC размера n=24.

Keywords

устойчивое паросочетание, матрица предпочтений, циклическое предпочтение, ориентированный взвешенный граф, устойчивый мэтчинг, контрпример

The name of the journal

Известия ВУЗов, Математика

On-line resource for training course

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

URL

https://doi.org/10.26907/0021-3446-2022-6-26-36

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

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

Resource files

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

Full metadata record

Field DC	Value	Language
dc.contributor.author	Lerner Eduard Yulevich	ru_RU
dc.date.accessioned	2022-01-01T00:00:00Z	ru_RU
dc.date.available	2022-01-01T00:00:00Z	ru_RU
dc.date.issued	2022	ru_RU
dc.identifier.citation	Лернер Э.Ю. Контрпримеры малого размера для трехмерной задачи поиска устойчивых мэтчингов с циклическими предпочтениями / Э.Ю. Лернер // Известия высших учебных заведений. Математика. - 2022. - № 6. - С. 26-36.	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=272139&p_lang=2	ru_RU
dc.description.abstract	Известия ВУЗов, Математика	ru_RU
dc.description.abstract	Рассмотрим n мужчин, n женщин и n собак, каждый мужчина имеет полный список предпочтений женщин, каждая женщина полный список предпочтений собак и каждая собака имеет полный список предпочтений мужчин (мы рассматриваем так называемую 3D-CYC problem --- трехмерную задачу с циклическими предпочтениями). Трисочетание есть набор n непересекающихся троек, содержащих по одному представителю каждого гендера. Трисочетание называется устойчивым (так называемым stable matching (SM)), если не существует мужчины, женщины и собаки из разных троек предпочитающих друг друга партнерам в своих тройках. Гиптотеза Eriksson, Sostrand и Strimling (2006) состояла в том, что задача отыскания SM (так называемая 3DSM-CYC задача) всегда имеет решение. Постепенно гипотеза была доказана для всех n<6. Однако, Lam и Paxton (2019) предложили алгоритм конструирования матриц предпочтений для 3DSM-CYC размера n=90, при которых M не существует. Вопрос о существовании контрпримеров меньшего размера оставался открытым. В этой работе мы построим наглядный контрпример для 3DSM-CYC размера n=24.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	устойчивое паросочетание	ru_RU
dc.subject	матрица предпочтений	ru_RU
dc.subject	циклическое предпочтение	ru_RU
dc.subject	ориентированный взвешенный граф	ru_RU
dc.subject	устойчивый мэтчинг	ru_RU
dc.subject	контрпример	ru_RU
dc.title	Контрпримеры малого размера для трехмерной задачи поиска устойчивых мэтчингов с циклическими предпочтениями	ru_RU
dc.type	Articles in Russian journals and collections	ru_RU