Статьи автора

СТАБИЛЬНЫЕ МАТЧИНГИ, ФУНКЦИИ ВЫБОРА И ЛИНЕЙНЫЕ ПОРЯДКИ

Номер выпуска 1 от 17.09.2025

В работе рассматривается модель стабильных реберных подмножеств (“матчингов”) в двудольном графе G = (V, E), в котором предпочтения для вершин одной доли (“фирм”) задаются при помощи функций выбора со стандартными свойствами консистентности, заменяемости и кардинальной монотонности, а предпочтения для вершин другой доли (“работников”) – при помощи линейных порядков. Для такой модели дается комбинаторное описание структуры ротаций и предлагается алгоритм построения посета ротаций с оценкой временн´ой сложности O(|E|2) (включая обращения к оракулам, связанных с функциями выбора). Как следствие, можно получить “компактное” аффинное представление стабильных матчингов и эффективно решать смежные задачи. Библ. 21.

24 0