Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BY - Uznanie autorstwaA Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
| dc.abstract.en | In the Bin Packing problem one is given n items with weights w1, …, wn and m bins with capacities c1, …, cm. The goal is to find a partition of the items into sets S1, …, Sm such that w(Sj) ≤ cj for every bin j, where w(X) denotes Σi∊xwi. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an time algorithm for Bin Packing. In this paper, we show that for every m ∊ ℕ there exists a constant σm > 0 such that an instance of Bin Packing with m bins can be solved in 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 δ > 0 there exists an ∊ > 0 such that if |{X ⊆ {1, …, n} : w(X) = v}| ≥ 2(1–∊)n for some v then |{w(X) : X ⊆ {1, …, n}}| ≤ 2δn. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Stany Zjednoczone |
| dc.conference.datefinish | 2021-01-13 |
| dc.conference.datestart | 2021-01-10 |
| dc.conference.place | Alexandria, Virginia (Virtual Conference) |
| dc.conference.series | ACM/SIAM Symposium on Discrete Algorithms |
| dc.conference.series | ACM/SIAM Symposium on Discrete Algorithms |
| dc.conference.seriesshortcut | SODA |
| dc.conference.shortcut | SODA 2021 |
| dc.conference.weblink | https://www.siam.org/conferences/cm/conference/soda21 |
| dc.contributor.author | Pawlewicz, Jakub |
| dc.contributor.author | Węgrzycki, Karol |
| dc.contributor.author | Swennenhuis, Celine |
| dc.contributor.author | Nederlof, Jesper |
| dc.date.accessioned | 2024-01-24T17:35:19Z |
| dc.date.available | 2024-01-24T17:35:19Z |
| dc.date.copyright | 2021-01-01 |
| dc.date.issued | 2021 |
| dc.description.accesstime | AT_PUBLICATION |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.version | FINAL_PUBLISHED |
| dc.identifier.doi | 10.1137/1.9781611976465.102 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/101537 |
| dc.identifier.weblink | https://doi.org/10.1137/1.9781611976465.102 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 1682-1701 |
| dc.rights | CC-BY |
| dc.sciencecloud | nosend |
| dc.title | A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |