Parameterized Algorithm
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.
- … 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".
- (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
- QUOTE: To cope with intractability, advanced techniques such as parameterized algorithms [10,13,31] (that isolate the exponential complexity to a specific structural parameter of a problem instance) and approximation algorithms [34] (that produce a solution whose value is guaranteed to be within a known factor of the value of an optimum solution) have been developed. But what can we say about finding exact solutions of non-parameterized instances of intractable problems? At first glance, the general case of an NP-complete problem is a formidable opponent: when faced with a problem whose instances can express arbitrary nondeterministic computation, how is one to proceed at solving a given instance, apart from the obvious exhaustive search that "tries out all the possibilities"?