*Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, Malte Skambath*:

**Solving Packing Problems with Few Small Items Using Rainbow Matchings.**

In *Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), *LIPIcs,
2020.

Go to website | Go to website | Show abstract

An important area of combinatorial optimization are packing problems. While fundamental problems like bin packing, multiple knapsack, and bin covering have been studied intensively from the viewpoint of approximation algorithms, the use of parameterized techniques for this problems is rather limited. For instances containing no "small'' items, known matching algorithms give exact polynomial-time algorithm. Following the distance from triviality approach, our parameter k is the distance from such easy instances, i. e., the number of small items.
Our main results are randomized fixed-parameter tractable algorithms for vector-versions of bin packing, multiple knapsack, and bin covering parameterized by k, which run in time 4^k * k! * n^O(1) with one-sided error. To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications as well. We also present a deterministic parameterized algorithm for bin packing with run time O( (k!)^2 * k * 2^k + n log(n) ).