| Форма представления | Статьи в российских журналах и сборниках |
| Год публикации | 2022 |
| Язык | русский |
|
Лернер Эдуард Юльевич, автор
|
| Библиографическое описание на языке оригинала |
Лернер Э.Ю. Контрпримеры малого размера для трехмерной задачи поиска устойчивых мэтчингов с циклическими предпочтениями / Э.Ю. Лернер // Известия высших учебных заведений. Математика. - 2022. - № 6. - С. 26-36. |
| Аннотация |
Рассмотрим 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. |
| Ключевые слова |
устойчивое паросочетание, матрица предпочтений, циклическое предпочтение, ориентированный взвешенный граф, устойчивый мэтчинг, контрпример |
| Название журнала |
Известия ВУЗов, Математика
|
| Ссылка для РПД |
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 |
| Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку |
https://repository.kpfu.ru/?p_id=272139 |
| Файлы ресурса | |
|
|
Полная запись метаданных  |
| Поле DC |
Значение |
Язык |
| dc.contributor.author |
Лернер Эдуард Юльевич |
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/?p_id=272139 |
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 |
Статьи в российских журналах и сборниках |
ru_RU |
|
EN 
中文 
ES 
Карта сайта
