Parameterized approximation algorithms for packing problems (Q313963): Difference between revisions

A (maximization) problem is fixed-parameter tractable (FPT) with respect to a parameter \(t\) if it can be solved in time \(O^\ast(f(t))\) for some function \(f\). If the best known polynomial-time approximation algorithm for the problem has approximation ratio \(\beta\), then for any approximation ratio \(\alpha<\beta\), if the value of an optimal solution is at least \(k\), we seek a solution of value at least \(\alpha k\) and we are interested in running times better than \(O^\ast(f(\alpha k))\). The main contribution of this paper is the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: The author introduces the definition of ``approximate lopsided universal sets'', combining partial executions of representative sets-based algorithms with approximation algorithms, and adapting the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Tradeoffs between \(O^\ast\) running times and approximation ratios are presented in the context of the well-known 3\textsc{-Set} \(k\)\textsc{-Packing}, \(P_2\)\textsc{-Packing} and 3\textsc{-Dimensional} \(k\)\textsc{-Matching} (3D \(k\)\textsc{-Matching}) problems. The following theorem has been proven for the tradeoff version of \(P_2\)\textsc{-Packing} with parameter \(\alpha\): \((\alpha, P_2)\)\textsc{-Packing} is solvable in deterministic time \(O^\ast \left(2^{o(k)}\cdot\frac{\binom{3k}{\alpha k}}{\binom{k}{\alpha k}}\right)\).