Arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{arxivlink|arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416| Мы разрабатываем новые алгоритмы аппр…») |
StasFomin (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели RAM при ограниченном пространстве. | Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели 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. | + | В качестве одного из наших основных результатов мы разработали алгоритм для набора «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). | + | В частности, это дает алгоритм аппроксимации с коэффициентом <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> биты пространства. | + | Для примеров проблем с ограниченной кратностью можно добиться большего. Мы разрабатываем алгоритм аппроксимации фактор-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-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> бит пространства. | Для независимого набора, ограниченного графами со средней степенью d, мы даем алгоритм аппроксимации с коэффициентом (2d), который работает за полиномиальное время и использует <m>O (log n)</m> бит пространства. | ||
| − | Мы также разработали алгоритм аппроксимации фактор — <m>O(d^2)</m> для доминирующего множества на d-вырожденных графах, который работает во времени <m>n^{O (log n)}</m> и использует <m>O(log^2n)</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> бит пространства. | + | Для d-регулярных графов мы покажем, как известный алгоритм приближения с рандомизированным коэффициентом <m>O(\log d)</m> может быть дерандомизирован для работы во времени <m>n^{O(1)}</m> и использования <m>O(\log n)</m> бит пространства. |
Наши результаты используют комбинацию идей теории ядра, распределенных алгоритмов и рандомизированных алгоритмов. | Наши результаты используют комбинацию идей теории ядра, распределенных алгоритмов и рандомизированных алгоритмов. | ||
Текущая версия на 10:44, 9 декабря 2021
Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели RAM при ограниченном пространстве.
В качестве одного из наших основных результатов мы разработали алгоритм для набора «d-ударов», который выполняется за время , использует бит пространства и достигает отношения приближения для любого положительного и любого натурального числа d.
В частности, это дает алгоритм аппроксимации с коэффициентом , который выполняется за время и использует бит пространства (для константы d).
Как следствие, мы получаем аналогичные оценки для вершинного покрытия и нескольких задач удаления графов.
Для примеров проблем с ограниченной кратностью можно добиться большего. Мы разрабатываем алгоритм аппроксимации фактор-2 для вершинного покрытия на графах с максимальной степенью и алгоритм для вычисления максимальных независимых множеств, которые выполняются за время и используют биты пространства.
Для более общей задачи d-Hitting Set мы разрабатываем алгоритм аппроксимации фактора d, который работает за время и использует биты пространства в наборах семейств, где каждый элемент встречается не более чем в наборах.
Для независимого набора, ограниченного графами со средней степенью d, мы даем алгоритм аппроксимации с коэффициентом (2d), который работает за полиномиальное время и использует бит пространства.
Мы также разработали алгоритм аппроксимации фактор — для доминирующего множества на d-вырожденных графах, который работает во времени и использует бит пространства.
Для d-регулярных графов мы покажем, как известный алгоритм приближения с рандомизированным коэффициентом может быть дерандомизирован для работы во времени и использования бит пространства.
Наши результаты используют комбинацию идей теории ядра, распределенных алгоритмов и рандомизированных алгоритмов.
…»