- Идеальная выборка моделей стохастического сопоставления с отказом (arXiv)
Автор:Томас Масанет, Паскаль Мойаль
Аннотация: В этой статье мы представляем небольшую вариацию алгоритма Кендалла «Доминируемая связь из прошлого» (DCFTP) для ограниченных цепей Маркова. Он основан на управлении (обычно немонотонной) стохастической рекурсией (обычно монотонной). Мы показываем, что этот алгоритм особенно подходит для моделей стохастического сопоставления с ограниченным терпением, класса моделей, для которых стационарное распределение системы в общем случае неизвестно в закрытой форме. Сначала мы покажем, что цепью Маркова этой модели можно легко управлять с помощью очереди с бесконечным количеством серверов. Затем мы исследуем частный случай, когда время терпения детерминировано, и этот аргумент контроля может не сработать. в этом случае мы прибегаем к специальной технике, которую также можно рассматривать как контроль (на этот раз по последовательности прибытия). Затем мы сравниваем этот алгоритм с классическим алгоритмом CFTP и показываем, как результаты нашего идеального моделирования можно использовать для оценки и сравнения вероятностей потерь различных систем, находящихся в равновесии.
2.Сила множественного выбора в стохастическом сопоставлении онлайн(arXiv)
Автор:Чжии Хуан, Синькай Шу, Шуи Ян
Аннотация: мы изучаем силу множественного выбора в стохастическом сопоставлении онлайн. Несмотря на длинную линию исследований, существующие алгоритмы до сих пор рассматривают только два выбора автономных соседей для каждой онлайн-вершины из-за технической сложности анализа нескольких вариантов. В этой статье представлены два подхода к разработке и анализу алгоритмов, использующих множественный выбор. Для невзвешенного и вершинно-взвешенного сопоставления мы применяем метод онлайн-коррелированного отбора (OCS) в стохастической настройке и улучшаем коэффициенты конкуренции до 0,716 с 0,711 и 0,7 соответственно. Для взвешенного сопоставления со свободным размещением мы предлагаем алгоритм Top Half Sampling. Мы напрямую характеризуем ход всего паросочетания, а не отдельных вершин, через дифференциальное неравенство. Это улучшает конкурентный коэффициент до 0,706, впервые в литературе преодолевая барьер 1-1e в этой настройке. Наконец, для более сложной задачи взвешивания по ребрам без свободного распоряжения мы доказываем, что никакие алгоритмы не могут быть конкурентоспособными на 0,703, отделяя эту настройку от трех вышеупомянутых.
3.Обобщенное стохастическое сопоставление(arXiv)
Автор:Алиреза Фархади, Джейкоб Гилберт, Мохаммад Таги Хаджиагайи
Аннотация: в этой статье мы обобщаем недавно изученную задачу стохастического сопоставления для более точного моделирования важного медицинского процесса, замены почек и некоторых других приложений. До сих пор изучалась задача стохастического сопоставления: для графа G = (V, E) каждое ребро включается в реализованный подграф графа независимо друг от друга с вероятностью p_e, и цель состоит в том, чтобы найти ограниченный по степени подграф Q графа G, который имеет ожидаемое максимальное соответствие, которое аппроксимирует ожидаемое максимальное соответствие реализованного подграфа. Эта модель не учитывает возможности выпадения вершин, которые можно найти в нескольких приложениях, например. при обмене почек, когда доноры или пациенты отказываются от процесса обмена, а также при онлайн-фрилансе и онлайн-знакомствах, когда обнаруживаются поддельные онлайн-профили. Таким образом, мы будем изучать более обобщенную модель стохастического сопоставления, в которой вершины и ребра реализуются независимо с некоторыми вероятностями p_v, p_e соответственно, что более точно подходит для важных приложений, чем ранее изученная модель. Мы обсудим первые алгоритмы и анализ этого обобщения модели стохастического сопоставления и докажем, что они обеспечивают хорошие коэффициенты аппроксимации. В частности, мы показываем, что коэффициент аппроксимации естественного алгоритма для этой задачи составляет не менее 0,6568 для невзвешенных графов и 1/2+ε для взвешенных графов для некоторой константы ε›0. Мы дополнительно улучшаем наш результат для невзвешенных графов до 2/3, используя подграфы с ограничениями степени ребра (EDCS).
