Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Alexandra Lassota, Aleksander Łukasiewicz, Adam Polak

We solve the Bin Packing problem in $O^{\ast }(2^k)$ time, where $k$ is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the…