TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Solving packing problems with few small items using rainbow matchings
 
Options

Solving packing problems with few small items using rainbow matchings

Citation Link: https://doi.org/10.15480/882.2882
Publikationstyp
Conference Paper
Date Issued
2020
Sprache
English
Author(s)
Bannach, Max  
Berndt, Sebastian  
Maack, Marten  
Mnich, Matthias  orcid-logo
Lassota, Alexandra  
Rau, Malin  
Skambath, Malte  
Institut
Algorithmen und Komplexität E-11  
TORE-DOI
10.15480/882.2882
TORE-URI
http://hdl.handle.net/11420/6533
First published in
Leibniz international proceedings in informatics (LIPIcs)  
Number in series
170
Start Page
11:1
End Page
11:14
Citation
International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Contribution to Conference
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)  
Publisher DOI
10.4230/LIPIcs.MFCS.2020.11
Scopus ID
2-s2.0-85090505183
ArXiv ID
2007.02660
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)).
Subjects
Bin Packing
Knapsack
matching
fixed-parameter tractable
DDC Class
004: Informatik
Funding(s)
Kernelisierung für große Datenmengen  
Multivariate Algorithmen für Scheduling mit hoher Multiplizität  
Lizenz
https://creativecommons.org/licenses/by/3.0/
Loading...
Thumbnail Image
Name

LIPIcs-MFCS-2020-11.pdf

Size

522.94 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback