Просмотр исходного текста страницы Arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416

{{checked|}}
{{arxivlink|arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416|
Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели RAM при ограниченном пространстве.  

В качестве одного из наших основных результатов мы разработали алгоритм для набора «d-ударов», который выполняется за время <m>n^{O(d^2 + d/\epsilon})}</m>, использует <m>O((d^2 + d / \epsilon) log n)</m> бит пространства и достигает отношения приближения <m>O ((d / {\epsilon}) n^{\epsilon})</m> для любого положительного <m>\epsilon \leq 1</m> и любого натурального числа d.  

В частности, это дает алгоритм аппроксимации с коэффициентом <m>O(\log n)</m>, который выполняется за время <m>n^{O (\log n)}</m> и использует <m>O(\log^2n)</m> бит пространства (для константы d).  

Как следствие, мы получаем аналогичные оценки для вершинного покрытия и нескольких задач удаления графов.

Для примеров проблем с ограниченной кратностью можно добиться большего.  Мы разрабатываем алгоритм аппроксимации фактор-2 для вершинного покрытия на графах с максимальной степенью <m>\Delta</m> и алгоритм для вычисления максимальных независимых множеств, которые выполняются за время <m>n^ {O (\ Delta)}</m> и используют <m>O(\Delta \log n)</m> биты пространства.  

Для более общей задачи d-Hitting Set мы разрабатываем алгоритм аппроксимации фактора d, который работает за время <m>n^{O (d {\delta}^2)}</m> и использует <m>O(d {\delta}^2 \log n)</m> биты пространства в наборах семейств, где каждый элемент встречается не более чем в <m>\delta</m> наборах.

Для независимого набора, ограниченного графами со средней степенью d, мы даем алгоритм аппроксимации с коэффициентом (2d), который работает за полиномиальное время и использует <m>O (log n)</m> бит пространства.  

Мы также разработали алгоритм аппроксимации фактор — <m>O(d^2)</m> для доминирующего множества на d-вырожденных графах, который работает во времени <m>n^{O(\log n)}</m> и использует <m>O(\log^2n)</m> бит пространства.  

Для d-регулярных графов мы покажем, как известный алгоритм приближения с рандомизированным коэффициентом <m>O(\log d)</m> может быть дерандомизирован для работы во времени <m>n^{O(1)}</m> и использования <m>O(\log n)</m> бит пространства.

Наши результаты используют комбинацию идей теории ядра, распределенных алгоритмов и рандомизированных алгоритмов. 
}}
{{enddiv}}

[[Категория:ArxivArticles]]