English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

An important area of combinatorial optimization is the study of packing andcovering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering.Those problems have been studied extensively from the viewpoint ofapproximation algorithms, but their parameterized complexity has only beeninvestigated barely. For problem instances containing no "small" items,classical matching algorithms yield optimal solutions in polynomial time. Inthis paper we approach them by their distance from triviality, measuring theproblem complexity by the number $k$ of small items.  Our main results are fixed-parameter algorithms for vector versions of BinPacking, Multiple Knapsack, and Bin Covering parameterized by $k$. Thealgorithms are randomized with one-sided error and run in time $4^{k} \cdot k!\cdot n^{O(1)}$. To achieve this, we introduce a colored matching problem towhich we reduce all these packing problems. The colored matching problem isnatural in itself and we expect it to be useful for other applications. We alsopresent a deterministic fixed-parameter for Bin Packing with run time$(k!)^{2}\cdot k \cdot 2^{k}\cdot n\cdot \log(n)$.

Solving Packing Problems with Few Small Items Using Rainbow Matchings