Form of presentation | Articles in Russian journals and collections |
Year of publication | 2022 |
Язык | русский |
|
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 | |
|
Full metadata record ![](https://shelly.kpfu.ru/pdf/picture/arrow_black_right.gif) |
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 |
|