Arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416
Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели RAM при ограниченном пространстве.
В качестве одного из наших основных результатов мы разработали алгоритм для набора «d-ударов», который выполняется за время , использует бит пространства и достигает отношения приближения для любого положительного и любого натурального числа d.
В частности, это дает алгоритм аппроксимации с коэффициентом , который выполняется за время и использует бит пространства (для константы d).
Как следствие, мы получаем аналогичные оценки для вершинного покрытия и нескольких задач удаления графов.
Для примеров проблем с ограниченной кратностью можно добиться большего. Мы разрабатываем алгоритм аппроксимации фактор-2 для вершинного покрытия на графах с максимальной степенью и алгоритм для вычисления максимальных независимых множеств, которые выполняются за время и используют биты пространства.
Для более общей задачи d-Hitting Set мы разрабатываем алгоритм аппроксимации фактора d, который работает за время и использует биты пространства в наборах семейств, где каждый элемент встречается не более чем в наборах.
Для независимого набора, ограниченного графами со средней степенью d, мы даем алгоритм аппроксимации с коэффициентом (2d), который работает за полиномиальное время и использует бит пространства.
Мы также разработали алгоритм аппроксимации фактор — для доминирующего множества на d-вырожденных графах, который работает во времени и использует бит пространства.
Для d-регулярных графов мы покажем, как известный алгоритм приближения с рандомизированным коэффициентом может быть дерандомизирован для работы во времени и использования бит пространства.
Наши результаты используют комбинацию идей теории ядра, распределенных алгоритмов и рандомизированных алгоритмов.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.