Name
Title | ||
|---|---|---|
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics |
Abstract | ||
|---|---|---|
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 to find a partition of the items into sets $S_1,\ldots,S_m$ such that $w(S_j) \leq c_j$ for every bin $j$, where $w(X)$ denotes $\sum_{i \in X}w_i$. Bj{\"{o}}rklund, Husfeldt and Koivisto (SICOMP 2009) presented an $\mathcal{O}^\star(2^n)$ time algorithm for Bin Packing. In this paper, we show that for every $m \in \mathbb{N}$ there exists a constant $\sigma_m >0$ such that an instance of Bin Packing 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 even for $m$ equals $4$ A key step in our approach is the following new result in Littlewood-Offord theory on the additive combinatorics of subset sums: For every $\delta >0$ there exists an $\varepsilon >0$ such that if $|\{ X\subseteq \{1,\ldots,n \} : w(X)=v \}| \leq 2^{(1-\varepsilon)n}$ for every $v$ then $|\{ w(X): X \subseteq \{1,\ldots,n\} \}|\leq 2^{\delta n}$. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/1.9781611976465.102 | SODA |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jesper Nederlof | 1 | 294 | 24.22 |
| Jakub Pawlewicz | 2 | 20 | 7.05 |
| Céline M. F. Swennenhuis | 3 | 0 | 0.68 |
| Karol Wegrzycki | 4 | 13 | 4.79 |