В теории вычислимости и теории сложности вычислений , особенно при изучении алгоритмов аппроксимации , приближение сохраняющего сокращения является алгоритмом для преобразования одной задачи оптимизации в другую проблему, так что расстояние решений от оптимального сохраняются до некоторой степени. Сохраняющие приближение редукции - это подмножество более общих редукций в теории сложности; разница в том, что редукции, сохраняющие аппроксимацию, обычно содержат утверждения о задачах аппроксимации или задачах оптимизации , а не о задачах решения .
Интуитивно проблема A сводится к проблеме B через редукцию, сохраняющую приближение, если, учитывая экземпляр проблемы A и (возможно, приближенный) решатель для проблемы B, можно преобразовать экземпляр проблемы A в экземпляр проблемы B, применить решатель для проблемы B, и восстановить решение для проблемы A, которое также имеет некоторую гарантию приближения.
Определение
В отличие от редукций в задачах решения, редукция с сохранением приближения должна сохранять больше, чем истинность экземпляров проблемы при редукции от одной проблемы к другой. Он также должен поддерживать некоторую гарантию связи между стоимостью решения и стоимостью оптимума в обеих задачах. Оформить:
Позволять а также быть проблемами оптимизации.
Позволять быть примером проблемы , с оптимальным решением . Позволять обозначить стоимость решения к экземпляру проблемы . Это также показатель, используемый для определения того, какое решение считается оптимальным.
Приближение сохраняющего сокращением является парой функций (который часто должен быть вычислим за полиномиальное время), так что:
- отображает экземпляр из к экземпляру из .
- отображает решение из к решению из .
- сохраняет некоторую гарантию решения по производительности , или коэффициент аппроксимации , определяемый как.
Типы
Существует множество различных типов редукций, сохраняющих приближение, и все они имеют разные гарантии (третий пункт в определении выше). Однако, в отличие от других редукций, редукции, сохраняющие приближение, часто перекрываются по тем свойствам, которые они демонстрируют в задачах оптимизации (например, членство в классе сложности или полнота, или несовместимость). Вместо этого используются различные типы сокращений в качестве различных методов сокращения, поскольку используется применимое сокращение, которое наиболее легко адаптируется к проблеме.
Не все типы сокращений, сохраняющих приближение, можно использовать для демонстрации принадлежности ко всем классам сложности аппроксимируемости, наиболее известными из которых являются PTAS и APX . Приведенная ниже редукция сохраняет членство в классе сложности C, если для задачи A, которая сводится к проблеме B с помощью схемы редукции, и B находится в C, то A также находится в C. Некоторые сокращения, показанные ниже, сохраняют только членство в APX или PTAS, но не другие. По этой причине при выборе сокращений, сохраняющих приближение, необходимо делать тщательный выбор, особенно с целью доказательства полноты проблемы в пределах класса сложности.
Крещенци предполагает, что тремя наиболее идеальными стилями сокращения, как с точки зрения простоты использования, так и с точки зрения доказательной силы, являются уменьшение PTAS, уменьшение AP и L-сокращение. [1] Приведенные ниже описания редукций взяты из обзора Крещенци редукций, сохраняющих приближение.
Строгое сокращение
Строгая редукция - это простейший вид редукции, сохраняющей приближение. При строгом сокращении отношение приближения решения y 'к экземпляру x' задачи B должно быть не более чем таким же хорошим, как отношение приближения соответствующего решения y к экземпляру x задачи A. Другими словами:
- for .
Strict reduction is the most straightforward: if a strict reduction from problem A to problem B exists, then problem A can always be approximated to at least as good a ratio as problem B. Strict reduction preserves membership in both PTAS and APX.
There exists a similar concept of an S-reduction, for which , and the optima of the two corresponding instances must have the same cost as well. S-reduction is a very special case of strict reduction, and is even more constraining. In effect, the two problems A and B must be in near-perfect correspondence with each other. The existence of an S-reduction implies not only the existence of a strict reduction but every other reduction listed here.
L-reduction
L-reductions preserve membership in PTAS as well as APX (but only for minimization problems in the case of the latter). As a result, they cannot be used in general to prove completeness results about APX, Log-APX, or Poly-APX, but nevertheless they are valued for their natural formulation and ease of use in proofs.[1]
PTAS-reduction
PTAS-reduction is another commonly used reduction scheme. Though it preserves membership in PTAS, it does not do so for APX. Nevertheless, APX-completeness is defined in terms of PTAS reductions.
PTAS-reductions are a generalization of P-reductions, shown below, with the only difference being that the function is allowed to depend on the approximation ratio .
A-reduction and P-reduction
A-reduction and P-reduction are similar reduction schemes that can be used to show membership in APX and PTAS respectively. Both introduce a new function , defined on numbers greater than 1, which must be computable.
In an A-reduction, we have that
- .
In a P-reduction, we have that
- .
The existence of a P-reduction implies the existence of a PTAS-reduction.
E-reduction
E-reduction, which is a generalization of strict reduction but implies both A-reduction and P-reduction, is an example of a less restrictive reduction style that preserves membership not only in PTAS and APX, but also the larger classes Log-APX and Poly-APX. E-reduction introduces two new parameters, a polynomial and a constant . Its definition is as follows.
In an E-reduction, we have that for some polynomial and constant ,
- , where denotes the size of the problem instance's description.
- For any solution to , we have .
To obtain an A-reduction from an E-reduction, let , and to obtain a P-reduction from an E-reduction, let .
AP-reduction
AP-reductions are used to define completeness in the classes Log-APX and Poly-APX. They are a special case of PTAS reduction, meeting the following restrictions.
In an AP-reduction, we have that for some constant ,
with the additional generalization that the function is allowed to depend on the approximation ratio , as in PTAS-reduction.
AP-reduction is also a generalization of E-reduction. An additional restriction actually needs to be imposed for AP-reduction to preserve Log-APX and Poly-APX membership, as E-reduction does: for fixed problem size, the computation time of must be non-increasing as the approximation ratio increases.
Gap reduction
A gap reduction is a type of reduction that, while useful in proving some inapproximability results, does not resemble the other reductions shown here. Gap reductions deal with optimization problems within a decision problem container, generated by changing the problem goal to distinguishing between the optimal solution and solutions some multiplicative factor worse than the optimum.
Смотрите также
Рекомендации
- ^ a b Crescenzi, Pierluigi (1997). "A Short Guide To Approximation Preserving Reductions". Proceedings of the 12th Annual IEEE Conference on Computational Complexity. Washington, D.C.: IEEE Computer Society: 262–. doi:10.1109/CCC.1997.612321. ISBN 0-8186-7907-7.