1. Эволюционное разбиение гиперграфа n-го уровня с адаптивным огрублением (arXiv)
Автор: Ричард Дж. Прин, Джим Смит
Аннотация. Разбиение гиперграфа — это NP-сложная задача, возникающая во многих приложениях информатики, где необходимо сводить большие задачи к ряду более мелких, поддающихся вычислительному решению подзадач. Современные методы используют многоуровневый подход, при котором начальное разбиение выполняется после сжатия гиперграфа до заданного уровня. Этот уровень обычно выбирается для создания очень грубых гиперграфов, в которых эвристические алгоритмы работают быстро и эффективно. В этой статье представлен новый меметический алгоритм, который остается эффективным на больших исходных гиперграфах. Это позволяет использовать информацию, которая может быть потеряна во время огрубления, и приводит к повышению качества конечного решения. Мы используем этот алгоритм, чтобы представить эмпирический анализ пространства возможных исходных гиперграфов с точки зрения его возможности поиска на различных уровнях укрупнения. Мы обнаружили, что наилучшие результаты получаются при уровнях укрупнения, уникальных для каждого гиперграфа. Основываясь на этом, мы вводим адаптивную схему, которая прекращает огрубление, когда скорость потери информации в гиперграфе становится нелинейной, и показываем, что это приводит к дальнейшим улучшениям. Результаты показывают, что мы определили ценную роль эволюционных алгоритмов в современной современной структуре разделения гиперграфов.
2. HYPE: массовое разбиение гиперграфа с расширением соседства (arXiv)
Автор: Кристиан Майер, Рубен Майер, Суканья Бховмик, Лукас Эппл, Курт Ротермель.
Вывод:многие важные приложения реального мира, такие как социальные сети или распределенные базы данных, могут быть смоделированы как гиперграфы. В такой модели вершины представляют объекты, такие как пользователи или записи данных, тогда как гиперребра моделируют групповое членство вершин, например, авторство в определенной теме или принадлежность записи данных к определенному реплицированному осколку. Чтобы оптимизировать такие приложения, нам нужно эффективное и действенное решение NP-жесткой сбалансированной проблемы разбиения гиперграфа k-way. Однако существующие разделители гиперграфов, которые масштабируются до очень больших графов, не эффективно используют структуру гиперграфа при принятии решений о разделении. Мы предлагаем HYPE, разделитель гиперграфов, который использует отношения соседства между вершинами в гиперграфе, используя эффективную реализацию расширения соседства. HYPE повышает качество разбиения на разделы до 95 % и сокращает время выполнения до 39 % по сравнению с потоковым разбиением.
3. Разбиение упорядоченных гиперграфов (arXiv)
Автор:Золтан Ф\ Уреди», Тао Цзян, Александр Косточка, Друв Мубайи, Жак Верстрате
Аннотация: {\em упорядоченный r-граф} — это r-однородный гиперграф, множество вершин которого линейно упорядочено. Для заданного 2≤k≤r упорядоченный r-граф H является {\em интервалом} k-{\em раздельным}, если существует не менее k непересекающихся интервалов в упорядочении, таких что каждое ребро H имеет непустое пересечение с каждым из интервалов и содержится в их объединении. Из нашего основного результата следует, что для любых α›k−1 и d›0 каждый n-вершинный упорядоченный r-граф с dnα ребрами имеет для некоторого m≤n m-вершинный интервальный k-дольный подграф с Ω(dmα) ребер. Это расширение для упорядоченных r-графов наблюдения Эрда Хоса и Клейтмана о том, что каждый r-граф содержит r-дольный подграф с постоянной долей ребер. Ограничение α›k−1 точное. Мы также представляем приложения основного результата к нескольким экстремальным задачам для упорядоченных гиперграфов.
