Better Bin Packing Approximations via Discrepancy Theory
From MaRDI portal
Publication:2816297
DOI10.1137/140955367zbMath1344.68099OpenAlexW2467941010MaRDI QIDQ2816297
Publication date: 4 July 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/140955367
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (7)
On the extension complexity of scheduling polytopes ⋮ Resource time-sharing for IoT applications with deadlines ⋮ Discrepancy theory and related algorithms ⋮ Unnamed Item ⋮ Linear discrepancy is \(\Pi_2\)-hard to approximate ⋮ Online bin packing of squares and cubes ⋮ Online bin packing of squares and cubes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- Discrepancy of set-systems and matrices
- ``Integer-making theorems
- Bin packing can be solved within 1+epsilon in linear time
- Roth's estimate of the discrepancy of integer sequences is nearly sharp
- The ellipsoid method and its consequences in combinatorial optimization
- Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem
- The Trim Problem
- Bin Packing via Discrepancy of Permutations
- The Design of Approximation Algorithms
- A Linear Programming Approach to the Cutting-Stock Problem
- Constructive Discrepancy Minimization by Walking on the Edges
- The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
- Six Standard Deviations Suffice
- Irregularities of Distribution, II
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
- Geometric discrepancy. An illustrated guide
This page was built for publication: Better Bin Packing Approximations via Discrepancy Theory
