Parameterized approximation algorithms for packing problems

We present tradeoffs that improve the running times of algorithms for well-known special cases of the 3-Setk-Packing problem at the cost of their accuracy. Consider a packing problem for which there is no known algorithm with approximation ratio α, and a parameter k. If the value of an optimal solution is at least k, we seek a solution of value at least αk; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value t runs in time O⁎(f(t)) for some function f, we are interested in running times better than O⁎(f(αk)). Our main contribution lies in the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: We introduce the definition of “approximate lopsided universal sets”, combine partial executions of representative sets-based algorithms with approximation algorithms, and adapt the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Our ideas are intuitive, and may be relevant to the design of other parameterized approximation algorithms.