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

We study the $d$-dimensional Vector Bin Packing ($d$VBP) problem, ageneralization of Bin Packing with central applications in resource allocationand scheduling. In $d$VBP, we are given a set of items, each of which ischaracterized by a $d$-dimensional volume vector; the objective is to partitionthe items into a minimum number of subsets (bins), such that the total volumeof items in each subset is at most $1$ in each dimension.  Our main result is an asymptotic approximation algorithm for $d$VBP thatyields a ratio of $(1+\ln d-\chi(d) +\varepsilon)$ for all $d \in \mathbb{N}$and any $\varepsilon > 0$; here, $\chi(d)$ is some strictly positive function.This improves upon the best known asymptotic ratio of $ \left(1+ \ln d+\varepsilon\right)$ due to Bansal, Caprara and Sviridenko (SICOMP 2010) forany $d >3$. By slightly modifying our algorithm to include an initial matchingphase and applying a tighter analysis we obtain an asymptotic approximationratio of $\left(\frac{4}{3}+\varepsilon\right)$ for the special case of $d=2$,thus substantially improving the previous best ratio of$\left(\frac{3}{2}+\varepsilon\right)$ due to Bansal, Elias and Khan (SODA2016).  Our algorithm iteratively solves a configuration LP relaxation for theresidual instance (from previous iterations) and samples a small number ofconfigurations based on the solution for the configuration LP. While iterativerounding was already used by Karmarkar and Karp (FOCS 1982) to establish theircelebrated result for classic (one-dimensional) Bin Packing, iterativerandomized rounding is used here for the first time in the context of (Vector)Bin Packing. Our results show that iterative randomized rounding is a powerfultool for approximating $d$VBP, leading to simple algorithms with improvedapproximation guarantees.

Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding