- Разрыхление графов с помощью универсальных жадных алгоритмов (arXiv)
Автор: Мин-Цзюнь Лай, Цзясинь Се, Чжицян Сюй
Аннотация: разреженность графа заключается в аппроксимации произвольного графа разреженным графом и полезна во многих приложениях, таких как упрощение социальных сетей, задачи наименьших квадратов, численное решение симметричных положительно определенных линейных систем и т. д. В этой статье, вдохновленной известным алгоритмом восстановления разреженного сигнала, называемым ортогональным поиском соответствия (OMP), мы вводим детерминированный жадный алгоритм выбора ребер, называемый универсальным жадным подходом (UGA) для разрежения графа. Для общей задачи спектральной разреженности, например, задачи выбора положительного подмножества из набора m векторов из Rn, мы предлагаем неотрицательный алгоритм UGA, который требует времени O(mn2+n3/ε2) для нахождения 1+ε/β1−ε/ β-спектральный разрежитель с положительными коэффициентами с разреженностью ≤⌈nε2⌉, где β — отношение наименьшей длины к наибольшей длине векторов. Будет установлена сходимость неотрицательного алгоритма UGA. Для задачи разрежения графа будет предложен другой алгоритм UGA, который может вывести 1+O(ε)1−O(ε)-спектральный разрежитель с ⌈nε2⌉ ребер за время O(m+n2/ε2) из графа с m ребер и n вершин при некоторых мягких предположениях. Это линейный по времени алгоритм с точки зрения количества ребер, которые ищет сообщество по разрежению графов. Наилучшим результатом в литературе, насколько известно авторам, является существование детерминированного алгоритма, который является почти линейным, т.е. O(m1+o(1)) для некоторого o(1)=O((loglog(m))2 /3log1/3(м)). Наконец, обширные экспериментальные результаты, в том числе приложения для кластеризации графов и регрессии методом наименьших квадратов, показывают эффективность предложенных подходов.
2. Разрежение ориентированных графов с помощью Cut Balance (arXiv)
Автор: Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, Kevin Sun
Аннотация: В этой статье мы рассматриваем задачу проектирования разрезающих разрыхлителей и скетчей для ориентированных графов. Чтобы обойти известные нижние границы, мы позволяем разрежателю/эскизу зависеть от баланса входного графа, который плавно интерполирует между неориентированными и ориентированными графами. Мы даем почти совпадающие верхние и нижние границы как для всех (см. Benczúr and Karger, STOC 1996), так и для каждого (Andoni et al., ITCS 2016) разрезающих разрежителей/эскизов в зависимости от баланса разрезов, определяя максимальное отношение значения отсечения в двух направлениях ориентированного графа (Эне и др., STOC 2016). Мы также показываем интересное применение разрежения орграфа через баланс разрезов, используя его для получения очень короткого доказательства знаменитого результата Каргера и Левина о максимальном потоке (STOC 2002).
3. Примечание о разрежении графа с сохранением расстояния (arXiv)
Автор:Грег Бодвин
Аннотация: мы рассматриваем задачи следующего типа: для заданного графа G сколько ребер потребуется в худшем случае для разреженного подграфа H, который приблизительно сохраняет расстояния между заданным набором пар узлов P? Примеры включают попарные гаечные ключи, средства сохранения расстояния, средства сохранения достижимости и т. д. Наблюдалась тенденция в области простых конструкций, основанных на методе совпадений множеств, за которыми последовали несколько более сложные конструкции, которые улучшают границы, полученные на основе множеств совпадений, примерно на логарифм. фактор. В этой заметке мы отмечаем, что более простые конструкции, основанные на наборах попаданий, на самом деле вообще не нуждаются в дополнительном логарифмическом коэффициенте. Это упрощает и объединяет несколько доказательств в этой области, а также улучшает размер попарного гаечного ключа +4 из O˜(np2/7) [Kavitha Th. Комп. Сис. ’17] до O(np2/7)
4. Разрежение графа для дерандомизации массовых параллельных вычислений с малым пространством (arXiv)
Автор:Артур Чумай, Питер Дэвис, Мерав Партер
Аннотация. Модель массовых параллельных вычислений (MPC) — это новая модель, в которой выделяются основные аспекты распределенных и параллельных вычислений. Он был разработан как инструмент для решения (обычно графических) задач в системах, в которых входные данные распределены по множеству машин с ограниченным пространством. Недавняя работа была сосредоточена на режиме, в котором машины имеют сублинейную (по n, количеству узлов во входном графе) память, с рандомизированными алгоритмами, представленными для фундаментальных графовых задач максимального соответствия и максимального независимого множества. Однако ранее соответствующих \emph{детерминированных} алгоритмов не существовало. Основная проблема, лежащая в основе настройки сублинейного пространства, заключается в том, что локальное пространство каждой машины может быть слишком маленьким для хранения всех ребер, относящихся к одному узлу. Это создает значительное препятствие по сравнению с классическими моделями, в которых предполагается, что каждый узел знает и имеет легкий доступ к своим инцидентным ребрам. Чтобы преодолеть этот барьер, мы вводим новый \emph{метод разреживания графа}, который \emph{детерминистически} вычисляет подграф низкого порядка с дополнительными требуемыми свойствами. Используя эту структуру для дерандомизации известного рандомизированного алгоритма Луби [SICOMP'86], мы получаем O(log∆+loglogn)-раундовых \emph{детерминированных} алгоритмов MPC для решения фундаментальных задач \emph{Максимального сопоставления} и \ emph{Максимальный независимый набор} с пространством O(nε) на каждой машине для любой константы ε›0. Основываясь на недавней работе Ghaffari et al. [FOCS’18] этот аддитивный коэффициент O(loglogn) является \emph{условно} существенным. Также можно показать, что эти алгоритмы работают за O(log∆) раундов в тесно связанной модели \congc, улучшая современную оценку O(log2∆) раундов, установленную Censor-Hillel et al. [ДИСК’17].
5. Алгоритмы динамических графов и разрыхление графов: новые методы и связи (arXiv)
Автор : Грамоз Горанчи
Вывод:графики естественным образом появляются в нескольких реальных контекстах, включая социальные сети, веб-сети и телекоммуникационные сети. В то время как анализ и понимание структур графов были центральной областью изучения при разработке алгоритмов, быстрое увеличение наборов данных за последние десятилетия поставило новые задачи для разработки эффективных алгоритмов, обрабатывающих крупномасштабные графы. Эти проблемы возникают из-за двух обычных предположений в разработке классических алгоритмов, а именно, что графы статичны и что они подходят для одной машины. Однако во многих предметных областях графы со временем часто изменяются, а их огромный размер делает невозможным их хранение в памяти одной машины. В связи с необходимостью разработки новых инструментов для решения таких проблем, эта диссертация посвящена двум областям разработки современных алгоритмов, которые непосредственно связаны с обработкой массивных графов, а именно алгоритмам динамических графов и разрежению графов. Мы разрабатываем новые алгоритмические методы как с точки зрения динамики, так и с точки зрения разреживания для множества задач оптимизации на основе графов, которые лежат в основе теории спектральных графов, разделения графов и метрических вложений. Наши алгоритмы быстрее, чем любые предыдущие, и разрабатывают меньшие разрежители с лучшим (приближенным) качеством. Что еще более важно, в этой работе представлены новые методы сокращения, которые показывают неожиданные связи между, казалось бы, разными областями, такими как алгоритмы динамического графа и разрежение графа.
