Arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416 — различия между версиями

«Approximation in (Poly-) Logarithmic Space 2020 2008.04416»^{скачать}

Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели RAM при ограниченном пространстве.

В качестве одного из наших основных результатов мы разработали алгоритм для набора «d-ударов», который выполняется за время , использует бит пространства и достигает отношения приближения для любого положительного , который выполняется за время и использует бит пространства (для константы d).

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

Для примеров проблем с ограниченной кратностью можно добиться большего. Мы разрабатываем алгоритм аппроксимации фактор-2 для вершинного покрытия на графах с максимальной степенью и алгоритм для вычисления максимальных независимых множеств, которые выполняются за время и используют биты пространства.

Для более общей задачи d-Hitting Set мы разрабатываем алгоритм аппроксимации фактора d, который работает за время и использует биты пространства в наборах семейств, где каждый элемент встречается не более чем в наборах.

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

Мы также разработали алгоритм аппроксимации фактор — для доминирующего множества на d-вырожденных графах, который работает во времени и использует бит пространства.

Для d-регулярных графов мы покажем, как известный алгоритм приближения с рандомизированным коэффициентом может быть дерандомизирован для работы во времени и использования бит пространства.

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