Схемы полиномиальной аппроксимации: типы и свойства
Polynomial-time approximation scheme
Полиномиальная схема аппроксимации (PTAS): алгоритмы для NP-трудных задач оптимизации. Гарантируют решение с точностью до (1+ε) от оптимального за полиномиальное время.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Тип алгоритма приближения
Type of approximation algorithm
В информатике (особенно в алгоритмике) схема полиномиального времени приближения (PTAS) — это тип алгоритма приближения для задач оптимизации (чаще всего, NP-трудных задач оптимизации). PTAS — это алгоритм, который принимает экземпляр задачи оптимизации и параметр ε > 0 и выдает решение, которое отличается от оптимального не более чем в (1 + ε) раз (или в (1 – ε) раз для задач максимизации). Например, для евклидовой задачи коммивояжера, PTAS выдаст маршрут длиной не более (1 + ε)L, где L — длина кратчайшего маршрута. Время работы PTAS должно быть полиномиальным относительно размера задачи для любого фиксированного ε, но может различаться для разных ε. Таким образом, алгоритм, работающий за время или даже , считается PTAS.
In computer science (particularly algorithmics), a polynomial time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and produces a solution that is within a factor 1 + ε of being optimal (or 1 – ε for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most (1 + ε)L, with L being the length of the shortest tour. The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time or even counts as a PTAS.
Детерминированный
Практическая проблема с алгоритмами PTAS заключается в том, что степень многочлена может резко возрастать при уменьшении ε, например, если время работы алгоритма составляет. Один из способов решения этой проблемы – определить эффективную полиномиальную схему аппроксимации времени (EPTAS), в которой время работы должно быть для некоторой константы c, не зависящей от ε. Это гарантирует, что увеличение размера задачи оказывает одинаковое относительное влияние на время работы, независимо от значения ε; однако, константа в асимптотической оценке "O" все еще может произвольно зависеть от ε. Иными словами, EPTAS работает за время FPT, где параметр – ε. Еще более строгим и полезным на практике является полностью полиномиальная схема аппроксимации времени (FPTAS), которая требует, чтобы время работы алгоритма было полиномиальным как от размера задачи n, так и от 1/ε. Если P ≠ NP, то FPTAS ⊂ PTAS ⊂ APX. Следовательно, при этом предположении, APX-трудные задачи не имеют PTAS. Другим детерминированным вариантом PTAS является квазиполиномиальная схема аппроксимации времени (QPTAS). QPTAS имеет временную сложность для каждого фиксированного ε > 0. Кроме того, PTAS может работать за время FPT для некоторой параметризации задачи, что приводит к параметризованной схеме аппроксимации.
A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is One way of addressing this is to define the efficient polynomial time approximation scheme or EPTAS, in which the running time is required to be for a constant c independent of ε. This ensures that an increase in problem size has the same relative effect on runtime regardless of what ε is being used; however, the constant under the big O can still depend on ε arbitrarily. In other words, an EPTAS runs in FPT time where the parameter is ε. Even more restrictive, and useful in practice, is the fully polynomial time approximation scheme or FPTAS, which requires the algorithm to be polynomial in both the problem size n and 1/ε. Unless P = NP, it holds that FPTAS ⊊ PTAS ⊊ APX. Consequently, under this assumption, APX hard problems do not have PTASs. Another deterministic variant of the PTAS is the quasi polynomial time approximation scheme or QPTAS. A QPTAS has time complexity for each fixed ε > 0. Furthermore, a PTAS can run in FPT time for some parameterization of the problem, which leads to a parameterized approximation scheme.
Рандомизированный
Некоторые задачи, для которых не существует PTAS, могут допускать рандомизированный алгоритм с аналогичными свойствами – схему полиномиального рандомизированного приближения (PRAS). PRAS – это алгоритм, который на вход получает экземпляр задачи оптимизации или подсчета и параметр ε > 0 и за полиномиальное время выдает решение, которое с высокой вероятностью находится в пределах ε от оптимального. Обычно под "высокой вероятностью" подразумевают вероятность, превышающую 3/4, хотя, как и в большинстве классов вероятностной сложности, определение устойчиво к изменениям этого точного значения (минимальным необходимым условием, как правило, является значение, превышающее 1/2). Как и PTAS, PRAS должен иметь полиномиальное время работы относительно размера входных данных n, но не обязательно относительно ε. При дополнительных ограничениях на время работы относительно ε можно определить эффективную схему полиномиального рандомизированного приближения (EPRAS), аналогичную EPTAS, и полностью полиномиальную схему рандомизированного приближения (FPRAS), аналогичную FPTAS.
Some problems which do not have a PTAS may admit a randomized algorithm with similar properties, a polynomial time randomized approximation scheme or PRAS. A PRAS is an algorithm which takes an instance of an optimization or counting problem and a parameter ε > 0 and, in polynomial time, produces a solution that has a high probability of being within a factor ε of optimal. Conventionally, "high probability" means probability greater than 3/4, though as with most probabilistic complexity classes the definition is robust to variations in this exact value (the bare minimum requirement is generally greater than 1/2). Like a PTAS, a PRAS must have running time polynomial in n, but not necessarily in ε; with further restrictions on the running time in ε, one can define an efficient polynomial time randomized approximation scheme or EPRAS similar to the EPTAS, and a fully polynomial time randomized approximation scheme or FPRAS similar to the FPTAS.
Как класс сложности
Термин PTAS также может использоваться для обозначения класса задач оптимизации, для которых существует PTAS. PTAS является подмножеством APX, и, если P ≠ NP, это строгое подмножество. Принадлежность к классу PTAS можно доказать с помощью PTAS-сведения, L-сведения или P-сведения, все из которых сохраняют принадлежность к PTAS и могут быть использованы для демонстрации PTAS-полноты. С другой стороны, доказательство того, что задача не принадлежит классу PTAS (то есть, что PTAS для нее не существует), может быть выполнено путем доказательства APX-трудности задачи, после чего существование PTAS привело бы к равенству P = NP. APX-трудность обычно доказывается с помощью PTAS-сведения или AP-сведения.
The term PTAS may also be used to refer to the class of optimization problems that have a PTAS. PTAS is a subset of APX, and unless P = NP, it is a strict subset. Membership in PTAS can be shown using a PTAS reduction, L reduction, or P reduction, all of which preserve PTAS membership, and these may also be used to demonstrate PTAS completeness. On the other hand, showing non membership in PTAS (namely, the nonexistence of a PTAS), may be done by showing that the problem is APX hard, after which the existence of a PTAS would show P = NP. APX hardness is commonly shown via PTAS reduction or AP reduction.