Approximation and online algorithms for multidimensional bin packing: a survey
From MaRDI portal
Publication:2400930
DOI10.1016/j.cosrev.2016.12.001zbMath1398.68007OpenAlexW2577702044MaRDI QIDQ2400930
Sebastian Pokutta, Prasad Tetali, Arindam Khan, Henrik I. Christensen
Publication date: 31 August 2017
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2016.12.001
online algorithmsapproximation algorithmsbin packinggeometric packingmultidimensional packing and coveringmultidimensional scheduling
Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Related Items
Asynchronous optimization of part logistics routing problem, An APTAS for bin packing with clique-graph conflicts, Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty, A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Adaptive simulated annealing with greedy search for the circle bin packing problem, Two dimensional guillotine cutting stock and scheduling problem in printing industry, A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing, On data reduction for dynamic vector bin packing, Online circle and sphere packing, Tight approximation algorithms for geometric bin packing with skewed items, An introduction to the two‐dimensional rectangular cutting and packing problem, Cutting and packing problems under uncertainty: literature review and classification framework, Peak demand minimization via sliced strip packing, There is no APTAS for 2-dimensional vector bin packing: revisited, Approximation algorithms for a virtual machine allocation problem with finite types, Three-Bar Charts Packing Problem, A mixed‐integer linear model for the multiple heterogeneous knapsack problem with realistic container loading constraints and bins' priority, Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints, A 4/3 OPT+2/3 approximation for big two-bar charts packing problem, Unnamed Item, An improved approximation for packing big two-bar charts, The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers, Efficient 1-space bounded hypercube packing algorithm, Improved Online Algorithms for Knapsack and GAP in the Random Order Model, Best fit bin packing with random order revisited, Online bin packing of squares and cubes, Vector scheduling with rejection on a single machine, Irreducible bin packing and normality in routing open shop, On Guillotine Separability of Squares and Rectangles., A Tight (3/2+ε) Approximation for Skewed Strip Packing., Online bin packing of squares and cubes, Unnamed Item, Complexity and inapproximability results for parallel task scheduling and strip packing, Exact solution techniques for two-dimensional cutting and packing, Improved online algorithms for Knapsack and GAP in the random order model, Fully dynamic bin packing revisited, Streaming algorithms for bin packing and vector scheduling, Closing the Gap for Pseudo-Polynomial Strip Packing, Two-bar charts packing problem, Algorithm for online 3-path vertex cover, Best Fit Bin Packing with Random Order Revisited, Techniques and results on approximation algorithms for packing circles, Adaptive Bin Packing with Overflow, A tight lower bound for the online bounded space hypercube bin packing problem, 2DPackLib: a two-dimensional cutting and packing library
Uses Software
Cites Work
- A simple on-line bin-packing algorithm
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Fast Approximation Algorithms for Knapsack Problems
- New Algorithms for Bin Packing
- Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
- Orthogonal Packings in Two Dimensions
- Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
- A algorithm for two-dimensional packing
- On Packing Two-Dimensional Bins
- A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
- Heuristic algorithms for on-line packing in three dimensions
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Better Bounds for Online Scheduling
- A Strip-Packing Algorithm with Absolute Performance Bound 2
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- Vector assignment problems: a general framework
- On approximating strip packing with a better ratio than 3/2
- Packing Small Vectors
- Improved Approximation for Vector Bin Packing
- Faster approximation schemes for the two-dimensional knapsack problem
- Online Lower Bounds via Duality
- About the Structure of the Integer Cone and its Application to Bin Packing
- Beating the Harmonic Lower Bound for Online Bin Packing
- Tight Bounds for Online Vector Scheduling
- Improved Pseudo-Polynomial-Time Approximation for Strip Packing
- On Multidimensional Packing Problems
- On-line bin packing in linear time
- On-line bin packing ? A restricted survey
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Coordination Complexity of Parallel Price-Directive Decomposition
- Optimal Analysis of Best Fit Bin Packing
- On Weighted Bipartite Edge Coloring.
- Algorithm Theory - SWAT 2004
- The optimal absolute ratio for online bin packing
- A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem
- Improved Approximation Algorithm for Two-Dimensional Bin Packing
- Polynomiality for Bin Packing with a Constant Number of Item Types
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
- Approximation Algorithms for 3D Orthogonal Knapsack
- Mathematical Foundations of Computer Science 2003
- Optimal Online Algorithms for Multidimensional Packing Problems
- Tight bounds for online vector bin packing
- On packing of squares and cubes
- Bounds for Certain Multiprocessing Anomalies
- The Loading Problem
- Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
- New Approximability Results for Two-Dimensional Bin Packing
- Algorithms and Computation
- LATIN 2004: Theoretical Informatics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Packing anchored rectangles
- Shelf algorithms for on-line strip packing
- There is no asymptotic PTAS for two-dimensional vector packing
- Book review of: A. Agnetis et al., Multiagent scheduling. Models and algorithms
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- A \((5/3+\varepsilon)\)-approximation for strip packing
- Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
- New lower bounds for certain classes of bin packing algorithms
- A note on online hypercube packing
- Improved online algorithms for parallel job scheduling and strip packing
- An on-line algorithm for multidimensional bin packing
- Approximating vector scheduling: almost matching upper and lower bounds
- There is no EPTAS for two-dimensional knapsack
- Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
- Completeness in approximation classes
- Rectangle packing with one-dimensional resource augmentation
- Maximizing the total profit of rectangles packed into a rectangle
- New algorithms for an ancient scheduling problem.
- Two-dimensional online bin packing with rotation
- A note on online strip packing
- Online algorithms for a dual version of bin packing
- Multidimensional on-line bin packing: Algorithms and worst-case analysis
- A 2.5 times optimal algorithm for packing in two dimensions
- Bin packing can be solved within 1+epsilon in linear time
- Lower bounds for on-line two-dimensional packing algorithms
- An improved lower bound for on-line bin packing algorithms
- Geometric algorithms and combinatorial optimization
- Resource constrained scheduling as generalized bin packing
- Approximation schemes for scheduling on parallel machines
- Differential approximation algorithms for some combinatorial optimization problems
- A branch-and-bound algorithm for the two-dimensional vector packing problem
- A better lower bound for on-line scheduling
- On some geometric methods in scheduling theory: A survey
- Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem
- On-line and off-line approximation algorithms for vector covering problems
- Online algorithms: a survey
- An asymptotic fully polynomial time approximation scheme for bin covering.
- On the two-dimensional knapsack problem
- Approximation algorithms for knapsack problems with cardinality constraints
- Offline first-fit decreasing height scheduling of power loads
- Multidimensional cube packing
- The two-dimensional cutting stock problem revisited
- Two-dimensional packing problems: a survey
- Two-dimensional on-line bin packing problem with rotatable items.
- An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
- Bin packing with fixed number of bins revisited
- Improved approximation for two dimensional strip packing with polynomial bounded width
- An improved deterministic rescaling for linear programming algorithms
- Absolute approximation ratios for packing rectangles into bins
- Two-dimensional bin packing with one-dimensional resource augmentation
- Bounds for online bounded space hypercube packing
- Carathéodory bounds for integer cones
- A 3-approximation algorithm for two-dimensional bin packing
- Vector assignment schemes for asymmetric settings
- Online square and cube packing
- Approximate strip packing: revisited
- Approximate Max-Min Resource Sharing for Structured Concave Optimization
- A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
- The Accommodating Function: A Generalization of the Competitive Ratio
- Online Multidimensional Load Balancing
- Improved Lower Bound for Online Strip Packing
- Bin Packing via Discrepancy of Permutations
- A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing
- This side up!
- The relative worst order ratio for online algorithms
- A Breakthrough in Sphere Packing: The Search for Magic Functions
- The Design of Approximation Algorithms
- Two for One: Tight Approximation of 2D Bin Packing
- A new upper bound 2.5545 on 2D Online Bin Packing
- On a dual version of the one-dimensional bin packing problem
- A Linear Programming Approach to the Cutting-Stock Problem
- Probabilistic analysis of algorithms for dual bin packing problems
- Handbook of Approximation Algorithms and Metaheuristics
- Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
- Constructive Discrepancy Minimization by Walking on the Edges
- Improved Bound for Online Square-into-Square Packing
- On the online bin packing problem
- On Three-Dimensional Packing
- A Polynomial Time Approximation Scheme for the Square Packing Problem
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Packing Rectangles into 2OPT Bins Using Rotations
- New Approximability Results for 2-Dimensional Packing Problems
- On the Sum-of-Squares algorithm for bin packing
- On strip packing With rotations
- A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
- Parameterized Approximation Scheme for the Multiple Knapsack Problem
- Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
- A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
- Shelf Algorithms for Two-Dimensional Packing Problems
