Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.2882
Publisher DOI: | 10.4230/LIPIcs.MFCS.2020.11 | arXiv ID: | 2007.02660 | Title: | Solving packing problems with few small items using rainbow matchings | Language: | English | Authors: | Bannach, Max Berndt, Sebastian Maack, Marten Mnich, Matthias ![]() Lassota, Alexandra Rau, Malin Skambath, Malte |
Keywords: | Bin Packing; Knapsack; matching; fixed-parameter tractable | Issue Date: | 2020 | Source: | International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) | Abstract (english): | 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 4k · k! · nO(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 Packing with run time O((k!)2 · k · 2k · n log(n)). |
Conference: | 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) | URI: | http://hdl.handle.net/11420/6533 | DOI: | 10.15480/882.2882 | ISBN: | 978-3-95977-159-7 | Institute: | Algorithmen und Komplexität E-11 | Document Type: | Chapter/Article (Proceedings) | Project: | Kernelisierung für große Datenmengen Multivariate Algorithmen für Scheduling mit hoher Multiplizität |
License: | ![]() |
Part of Series: | Leibniz international proceedings in informatics (LIPIcs) | Volume number: | 170 |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-MFCS-2020-11.pdf | Verlagsversion | 522,94 kB | Adobe PDF | View/Open![]() |
Page view(s)
351
Last Week
2
2
Last month
6
6
checked on Jun 2, 2023
Download(s)
130
checked on Jun 2, 2023
SCOPUSTM
Citations
1
Last Week
0
0
Last month
0
0
checked on Jun 30, 2022
Google ScholarTM
Check
Note about this record
Cite this record
Export
This item is licensed under a Creative Commons License