A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
From MaRDI portal
Publication:6089980
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
Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Randomized algorithms (68W20) Arithmetic combinatorics; higher degree uniformity (11B30)
Related Items
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