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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In the Bin Packing problem one is given $n$ items with weights$w_1,\ldots,w_n$ and $m$ bins with capacities $c_1,\ldots,c_m$. The goal is tofind a partition of the items into sets $S_1,\ldots,S_m$ such that $w(S_j) \leqc_j$ for every bin $j$, where $w(X)$ denotes $\sum_{i \in X}w_i$. Bj\"orklund,Husfeldt and Koivisto (SICOMP 2009) presented an $\mathcal{O}^\star(2^n)$ timealgorithm for Bin Packing. In this paper, we show that for every $m \in\mathbf{N}$ there exists a constant $\sigma_m >0$ such that an instance of BinPacking with $m$ bins can be solved in $\mathcal{O}(2^{(1-\sigma_m)n})$randomized time. Before our work, such improved algorithms were not known evenfor $m$ equals $4$. A key step in our approach is the following new result inLittlewood-Offord theory on the additive combinatorics of subset sums: Forevery $\delta >0$ there exists an $\varepsilon >0$ such that if $|\{ X\subseteq\{1,\ldots,n \} : w(X)=v \}| \geq 2^{(1-\varepsilon)n}$ for some $v$ then $|\{w(X): X \subseteq \{1,\ldots,n\} \}|\leq 2^{\delta n}$.

A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics