Parameterized Algorithm

From GM-RKB
Jump to navigation Jump to search

See: Algorithm, Approximation Algorithm, Exact Exponential Algorithm, Optimization Algorithm, Local Search Algorithm, Estimation Algorithm, Vertex Cover Task.



References

2013

  • http://en.wikipedia.org/wiki/Parameterized_complexity
    • … Under the assumption that P ≠ NP, there exist many natural problems that require superpolynomial running time when complexity is measured in terms of the input size only, but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter k. Hence, if k is fixed at a small value and the growth of the function over k is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable".

      … Problems in which some parameter k is fixed are called parameterized problems. A parameterized problem that allows for such an fpt-algorithm is said to be a fixed-parameter tractable problem and belongs to the class [math]\displaystyle{ FPT }[/math], and the early name of the theory of parameterized complexity was fixed-parameter tractability.

      Many problems have the following form: given an object [math]\displaystyle{ x }[/math] and a nonnegative integer k, does x have some property that depends on k? For instance, for the vertex cover problem, the parameter can be the number of vertices in the cover. In many applications, for example when modelling error correction, one can assume the parameter to be "small" compared to the total input size. Then it is interesting to see whether we can find an algorithm which is exponential only in k, and not in the input size.

  • (Fomin & Kaski, 2013) ⇒ Fedor V. Fomin, and Petteri Kaski. (2013). “Exact Exponential Algorithms.” In: Communications of the ACM Journal, 56(3). doi:10.1145/2428556.2428575