2026-08-17T04:49:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12681 2024-03-06T10:50:33Z ddc:004 open_access

Solving Packing Problems with Few Small Items Using Rainbow Matchings Bannach, Max Berndt, Sebastian Maack, Marten Mnich, Matthias Lassota, Alexandra Rau, Malin Skambath, Malte Bin Packing Knapsack matching fixed-parameter tractable An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no "small" items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items. Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4^k⋅ k!⋅ n^{O(1)}. 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. We also present a deterministic fixed-parameter algorithm for Bin Covering with run time O((k!)² ⋅ k ⋅ 2^k ⋅ n log(n)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Bannach and Sebastian Berndt and Marten Maack and Matthias Mnich and Alexandra Lassota and Malin Rau and Malte Skambath 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.11 urn:nbn:de:0030-drops-126816 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.11 eng https://creativecommons.org/licenses/by/3.0/legalcode