- Модель стохастического сопоставления на общих графических структурах(arXiv)
Автор: Юссеф Раме
Аннотация: Руководствуясь широким спектром систем сборки на заказ и систем совместной экономики, мы представляем модель стохастического сопоставления на гиперграфах и мультиграфах, расширяя модель, представленную Майрессом и Мойалом, 2016. В этой диссертации модель стохастического сопоставления (S, Φ, μ) на общих структурах графа определяется следующим образом: при заданной общей структуре графа совместимости S = (V, S) какой из множества узлов, обозначенных V, которые представляют классы элементов и набором ребер, обозначенным S, который позволяет сопоставлять различные классы элементов. Элементы поступают в систему в случайное время в виде последовательности (предположительно, i.i.d.), состоящей из различных классов V, и требуют сопоставления из-за их совместимости в соответствии с S. Совместимость по группам из двух или более (гиперграфический падежи) и группами по два с возможностью сопоставления предметов одного класса (мультиграфические падежи). Несопоставленные элементы хранятся в системе и ждут будущего совместимого элемента, и как только они совпадают, они оставляют его вместе. По прибытии элемент может найти несколько возможных совпадений, элементы, покидающие систему, зависят от заданной политики сопоставления Φ. Мы изучаем устойчивость модели стохастического соответствия на гиперграфах для различных гиперграфических топологий. Затем устойчивость модели стохастического сопоставления на мультиграфах с использованием максимального подграфа и минимального раздутия для выделения зоны устойчивости
2. Онлайн-сопоставление стохастиков, приходы Пуассона и программа естественной линейной зависимости(arXiv)
Автор: Чжи Хуан, Синькай Шу
Аннотация: мы изучаем онлайн-проблему стохастического сопоставления. Рассмотрим двудольный граф с автономными вершинами на одной стороне и с i.i.d.онлайн-вершинами на другой стороне. Оффлайн-вершины и распределение онлайн-вершин заранее известны алгоритму. Однако реализация онлайн-вершин раскрывается по одной, после чего алгоритм немедленно решает, как ее сопоставить. Для максимизации мощности сопоставления мы даем 0,711-конкурентный онлайн-алгоритм, который улучшает лучшее предыдущее соотношение 0,706. Когда автономные вершины взвешиваются, мы вводим конкурентный онлайн-алгоритм 0,7009 для максимизации общего веса совпадающих автономных вершин, который улучшает наилучшее предыдущее соотношение 0,662. Концептуально мы обнаруживаем, что анализ онлайн-алгоритмов упрощается, если онлайн-вершины следуют пуассоновскому процессу, и устанавливаем приблизительную эквивалентность между этой пуассоновской моделью прибытия и онлайн-стохстическим сопоставлением. С технической точки зрения мы предлагаем естественную линейную программу для модели прихода Пуассона и демонстрируем, как использовать ее структуру, вводя обратное неравенство Дженсена. Более того, мы разрабатываем алгоритмическую амортизацию для замены аналитической в предыдущей работе, и в результате получаем первый взвешенный по вершинам онлайн-алгоритм стохастического сопоставления, который улучшает результаты в более слабой модели случайных поступлений.
3.Стохастическое динамическое сопоставление: смешанный подход теории графов и линейной алгебры(arXiv)
Автор:Селин Конт, Фабьен Матье, Ана Бушич
Аннотация:Задачи стохастического динамического сопоставления недавно привлекли внимание в сообществе стохастического моделирования из-за их многочисленных приложений, начиная от управления цепочками поставок и заканчивая программами обмена почек. В этой статье мы рассматриваем задачу сопоставления, в которой элементы разных классов поступают в соответствии с независимыми пуассоновскими процессами. Несопоставленные элементы хранятся в очереди, а ограничения совместимости описываются простым графом классов, так что два элемента могут сопоставляться, если их классы являются соседними в графе. Мы анализируем эффективность политик сопоставления не только с точки зрения стабильности системы, но и с точки зрения коэффициентов сопоставления между различными классами. Наши результаты основаны на наблюдении, что при любой стабильной политике коэффициенты совпадения удовлетворяют уравнению сохранения, которое уравнивает коэффициенты прибытия и отправления каждого класса предметов. Наш основной вклад тройной. Сначала мы вводим отображение между размерностью множества решений этого уравнения сохранения, структурой графа совместимости и существованием стабильной политики. В частности, это позволяет вывести необходимое и достаточное условие устойчивости, проверяемое за полиномиальное время. Во-вторых, мы описываем выпуклый многогранник неотрицательных решений уравнения сохранения. Когда этот многогранник сводится к одной точке, мы даем решение в замкнутой форме; вообще говоря, мы характеризуем вершины этого многогранника, используя снова структуру графа. Наконец, мы изучаем части многогранника, которые могут быть достигнуты с помощью стабильной политики. Показано, что жадные политики ограничены внутренностью многогранника при строгом включении вообще. Напротив, нежадные политики могут достигать любой точки внутренности этого многогранника, а также достигать границы многогранника в зависимости от простого условия на вершинах
