StasFomin в 10:44, 9 декабря 2021

2021-12-09T10:44:55Z

StasFomin: Новая страница: «{{checked|}} {{arxivlink|arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416| Мы разрабатываем новые алгоритмы аппр…»

2021-12-09T10:43:04Z

Новая страница: «{{checked|}} {{arxivlink|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]]

@@ Строка 3: / Строка 3: @@
 Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели 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> бит пространства.
-Мы также разработали алгоритм аппроксимации фактор — <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> бит пространства.
 Наши результаты используют комбинацию идей теории ядра, распределенных алгоритмов и рандомизированных алгоритмов.

Arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416 - История изменений

StasFomin в 10:44, 9 декабря 2021

StasFomin: Новая страница: «{{checked|}} {{arxivlink|arxiv/Approximation in (Poly-) Logarithmic Space 2020 2008.04416| Мы разрабатываем новые алгоритмы аппр…»