By this author

STABLE MATCHINGS, CHOICE FUNCTIONS, AND LINEAR ORDERS

Issue number 1 from 17.09.2025

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

24 0