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

DOI10.1137/22m1478112zbMath1529.68186arXiv2007.08204OpenAlexW4389146350MaRDI QIDQ6089980

Jakub Pawlewicz, Céline M. F. Swennenhuis, Jesper Nederlof, Karol Węgrzycki

Publication date: 15 December 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.08204

zbMATH Keywords

algorithmsbin packingadditive combinatoricsLittlewood-Offord theory

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Randomized algorithms (68W20) Arithmetic combinatorics; higher degree uniformity (11B30)

Related Items

Computing generalized convolutions faster than brute force

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• Polynomial kernels for weighted problems
• Improved approximation of linear threshold functions
• On an extension of the Sort \& Search method with application to scheduling theory
• Exact exponential algorithms.
• An application of simultaneous diophantine approximation in combinatorial optimization
• Bin packing with fixed number of bins revisited
• Singularity of random Bernoulli matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Mathematical Methods of Organizing and Planning Production
• The Trim Problem
• Anti-concentration for polynomials of independent random variables
• Reducing a Target Interval to a Few Exact Queries
• Improved Generic Algorithms for Hard Knapsacks
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Counting Paths and Packings in Halves
• Partitioning into Sets of Bounded Cardinality
• Computing Partitions with Applications to the Knapsack Problem
• Estimates for the concentration function of combinatorial number theory and probability
• An upper bound for codes in a two-access binary erasure channel (Corresp.)
• Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
• A Logarithmic Additive Integrality Gap for Bin Packing
• Dense Subset Sum may be the hardest
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• On Problems as Hard as CNF-SAT
• Families with Infants
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
• Anticoncentration versus the Number of Subset Sums
• Families with Infants: A General Approach to Solve Hard Partition Problems
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Parameterized Algorithms
• The Loading Problem
• Information Theory and Statistics: A Tutorial

This page was built for publication: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics