= Solution
A parameterized <decision problem> is <fixed-parameter tractable> if there is an <algorithm> deciding inputs of encoded length $N$ and parameter $k$ in <running time> at most \b[$f(k)N^c$], where $f$ is a computable <function> and $c$ is a constant independent of $k$. Arbitrarily expensive dependence on the parameter is permitted; putting $k$ in the exponent of $N$ does not by itself establish <fixed-parameter tractability>.
For a minimization problem with nonnegative costs, a factor-two <approximation algorithm> runs in <polynomial time>, always returns a <feasible solution>, and satisfies \b[$\operatorname{cost}(\operatorname{ALG})\leq2\operatorname{OPT}$] on every feasible input. A <feasible solution> also satisfies $\operatorname{OPT}\leq\operatorname{cost}(\operatorname{ALG})$. If the optimum is zero, the guarantee requires an answer of zero cost.
Back to article page
