Approximation and online algorithms for multidimensional bin packing: a survey (Q2400930): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.cosrev.2016.12.001
+Normal rank
@@ Property / OpenAlex ID @@
+W2577702044
@@ Property / OpenAlex ID: W2577702044 / rank @@
+Normal rank
@@ Property / cites work @@
+A Linear Programming Approach to the Cutting-Stock Problem
+Normal rank
@@ Property / cites work @@
+The Loading Problem
@@ Property / cites work: The Loading Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Q4658190
@@ Property / cites work: Q4658190 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4133108
@@ Property / cites work: Q4133108 / rank @@
+Normal rank
@@ Property / cites work @@
+Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002852
@@ Property / cites work: Q3002852 / rank @@
+Normal rank
@@ Property / cites work @@
+Handbook of Approximation Algorithms and Metaheuristics
+Normal rank
@@ Property / cites work @@
+Q4223058
@@ Property / cites work: Q4223058 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3347319
@@ Property / cites work: Q3347319 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4002885
@@ Property / cites work: Q4002885 / rank @@
+Normal rank
@@ Property / cites work @@
+On-line bin packing ? A restricted survey
@@ Property / cites work: On-line bin packing ? A restricted survey / rank @@
+Normal rank
@@ Property / cites work @@
+Q3145801
@@ Property / cites work: Q3145801 / rank @@
+Normal rank
@@ Property / cites work @@
+Shelf algorithms for on-line strip packing
@@ Property / cites work: Shelf algorithms for on-line strip packing / rank @@
+Normal rank
@@ Property / cites work @@
+A branch-and-bound algorithm for the two-dimensional vector packing problem
+Normal rank
@@ Property / cites work @@
+Orthogonal Packings in Two Dimensions
@@ Property / cites work: Orthogonal Packings in Two Dimensions / rank @@
+Normal rank
@@ Property / cites work @@
+Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
+Normal rank
@@ Property / cites work @@
+Two-dimensional packing problems: a survey
@@ Property / cites work: Two-dimensional packing problems: a survey / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for metric facility location and             <i>k</i>             -Median problems using the primal-dual schema and Lagrangian relaxation
+Normal rank
@@ Property / cites work @@
+The Design of Approximation Algorithms
@@ Property / cites work: The Design of Approximation Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness in approximation classes
@@ Property / cites work: Completeness in approximation classes / rank @@
+Normal rank
@@ Property / cites work @@
+Online algorithms: a survey
@@ Property / cites work: Online algorithms: a survey / rank @@
+Normal rank
@@ Property / cites work @@
+Q4875207
@@ Property / cites work: Q4875207 / rank @@
+Normal rank
@@ Property / cites work @@
+The Accommodating Function: A Generalization of the Competitive Ratio
+Normal rank
@@ Property / cites work @@
+The relative worst order ratio for online algorithms
+Normal rank
@@ Property / cites work @@
+Differential approximation algorithms for some combinatorial optimization problems
+Normal rank
@@ Property / cites work @@
+Bin packing can be solved within 1+epsilon in linear time
+Normal rank
@@ Property / cites work @@
+An improved deterministic rescaling for linear programming algorithms
+Normal rank
@@ Property / cites work @@
+A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
+Normal rank
@@ Property / cites work @@
+Q2957914
@@ Property / cites work: Q2957914 / rank @@
+Normal rank
@@ Property / cites work @@
+Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
+Normal rank
@@ Property / cites work @@
+Optimal Analysis of Best Fit Bin Packing
@@ Property / cites work: Optimal Analysis of Best Fit Bin Packing / rank @@
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Fast Approximation Algorithms for Fractional Packing and Covering Problems
+Normal rank
@@ Property / cites work @@
+Q2913806
@@ Property / cites work: Q2913806 / rank @@
+Normal rank
@@ Property / cites work @@
+Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem
+Normal rank
@@ Property / cites work @@
+Bin Packing via Discrepancy of Permutations
@@ Property / cites work: Bin Packing via Discrepancy of Permutations / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743405
@@ Property / cites work: Q5743405 / rank @@
+Normal rank
@@ Property / cites work @@
+Constructive Discrepancy Minimization by Walking on the Edges
+Normal rank
@@ Property / cites work @@
+Polynomiality for Bin Packing with a Constant Number of Item Types
+Normal rank
@@ Property / cites work @@
+About the Structure of the Integer Cone and its Application to Bin Packing
+Normal rank
@@ Property / cites work @@
+Bin packing with fixed number of bins revisited
@@ Property / cites work: Bin packing with fixed number of bins revisited / rank @@
+Normal rank
@@ Property / cites work @@
+A simple on-line bin-packing algorithm
@@ Property / cites work: A simple on-line bin-packing algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+On-line bin packing in linear time
@@ Property / cites work: On-line bin packing in linear time / rank @@
+Normal rank
@@ Property / cites work @@
+On the online bin packing problem
@@ Property / cites work: On the online bin packing problem / rank @@
+Normal rank
@@ Property / cites work @@
+Beating the Harmonic Lower Bound for Online Bin Packing
+Normal rank
@@ Property / cites work @@
+New lower bounds for certain classes of bin packing algorithms
+Normal rank
@@ Property / cites work @@
+An improved lower bound for on-line bin packing algorithms
+Normal rank
@@ Property / cites work @@
+The optimal absolute ratio for online bin packing
@@ Property / cites work: The optimal absolute ratio for online bin packing / rank @@
+Normal rank
@@ Property / cites work @@
+On the Sum-of-Squares algorithm for bin packing
@@ Property / cites work: On the Sum-of-Squares algorithm for bin packing / rank @@
+Normal rank
@@ Property / cites work @@
+Offline first-fit decreasing height scheduling of power loads
+Normal rank
@@ Property / cites work @@
+An asymptotic fully polynomial time approximation scheme for bin covering.
+Normal rank
@@ Property / cites work @@
+On Weighted Bipartite Edge Coloring.
@@ Property / cites work: On Weighted Bipartite Edge Coloring. / rank @@
+Normal rank
@@ Property / cites work @@
+On packing of squares and cubes
@@ Property / cites work: On packing of squares and cubes / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
+Normal rank
@@ Property / cites work @@
+Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
+Normal rank
@@ Property / cites work @@
+A Strip-Packing Algorithm with Absolute Performance Bound 2
+Normal rank
@@ Property / cites work @@
+Approximate Max-Min Resource Sharing for Structured Concave Optimization
+Normal rank
@@ Property / cites work @@
+A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
+Normal rank
@@ Property / cites work @@
+There is no EPTAS for two-dimensional knapsack
@@ Property / cites work: There is no EPTAS for two-dimensional knapsack / rank @@
+Normal rank
@@ Property / cites work @@
+New Approximability Results for Two-Dimensional Bin Packing
+Normal rank
@@ Property / cites work @@
+Q2934716
@@ Property / cites work: Q2934716 / rank @@
+Normal rank
@@ Property / cites work @@
+A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithm for Two-Dimensional Bin Packing
+Normal rank
@@ Property / cites work @@
+Improved Approximation for Vector Bin Packing
@@ Property / cites work: Improved Approximation for Vector Bin Packing / rank @@
+Normal rank
@@ Property / cites work @@
+On Packing Two-Dimensional Bins
@@ Property / cites work: On Packing Two-Dimensional Bins / rank @@
+Normal rank
@@ Property / cites work @@
+A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
+Normal rank
@@ Property / cites work @@
+LATIN 2004: Theoretical Informatics
@@ Property / cites work: LATIN 2004: Theoretical Informatics / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Online Algorithms for Multidimensional Packing Problems
+Normal rank
@@ Property / cites work @@
+On strip packing With rotations
@@ Property / cites work: On strip packing With rotations / rank @@
+Normal rank
@@ Property / cites work @@
+Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
+Normal rank
@@ Property / cites work @@
+A 3-approximation algorithm for two-dimensional bin packing
+Normal rank
@@ Property / cites work @@
+Absolute approximation ratios for packing rectangles into bins
+Normal rank
@@ Property / cites work @@
+Packing Rectangles into 2OPT Bins Using Rotations
@@ Property / cites work: Packing Rectangles into 2OPT Bins Using Rotations / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
+Normal rank
@@ Property / cites work @@
+Two for One: Tight Approximation of 2D Bin Packing
+Normal rank
@@ Property / cites work @@
+Multidimensional on-line bin packing: Algorithms and worst-case analysis
+Normal rank
@@ Property / cites work @@
+An on-line algorithm for multidimensional bin packing
+Normal rank
@@ Property / cites work @@
+Q4828973
@@ Property / cites work: Q4828973 / rank @@
+Normal rank
@@ Property / cites work @@
+A new upper bound 2.5545 on 2D Online Bin Packing
@@ Property / cites work: A new upper bound 2.5545 on 2D Online Bin Packing / rank @@
+Normal rank
@@ Property / cites work @@
+Two-dimensional on-line bin packing problem with rotatable items.
+Normal rank
@@ Property / cites work @@
+Two-dimensional online bin packing with rotation
@@ Property / cites work: Two-dimensional online bin packing with rotation / rank @@
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2003
@@ Property / cites work: Mathematical Foundations of Computer Science 2003 / rank @@
+Normal rank
@@ Property / cites work @@
+This side up!
@@ Property / cites work: This side up! / rank @@
+Normal rank
@@ Property / cites work @@
+Multidimensional cube packing
@@ Property / cites work: Multidimensional cube packing / rank @@
+Normal rank
@@ Property / cites work @@
+Online square and cube packing
@@ Property / cites work: Online square and cube packing / rank @@
+Normal rank
@@ Property / cites work @@
+A note on online hypercube packing
@@ Property / cites work: A note on online hypercube packing / rank @@
+Normal rank
@@ Property / cites work @@
+Bounds for online bounded space hypercube packing
@@ Property / cites work: Bounds for online bounded space hypercube packing / rank @@
+Normal rank
@@ Property / cites work @@
+Two-dimensional bin packing with one-dimensional resource augmentation
+Normal rank
@@ Property / cites work @@
+A 2.5 times optimal algorithm for packing in two dimensions
+Normal rank
@@ Property / cites work @@
+A \((5/3+\varepsilon)\)-approximation for strip packing
+Normal rank
@@ Property / cites work @@
+On approximating strip packing with a better ratio than 3/2
+Normal rank
@@ Property / cites work @@
+Improved Pseudo-Polynomial-Time Approximation for Strip Packing
+Normal rank
@@ Property / cites work @@
+Improved approximation for two dimensional strip packing with polynomial bounded width
+Normal rank
@@ Property / cites work @@
+Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
+Normal rank
@@ Property / cites work @@
+A algorithm for two-dimensional packing
@@ Property / cites work: A algorithm for two-dimensional packing / rank @@
+Normal rank
@@ Property / cites work @@
+Rectangle packing with one-dimensional resource augmentation
+Normal rank
@@ Property / cites work @@
+Shelf Algorithms for Two-Dimensional Packing Problems
+Normal rank
@@ Property / cites work @@
+Approximate strip packing: revisited
@@ Property / cites work: Approximate strip packing: revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for on-line two-dimensional packing algorithms
+Normal rank
@@ Property / cites work @@
+Improved Lower Bound for Online Strip Packing
@@ Property / cites work: Improved Lower Bound for Online Strip Packing / rank @@
+Normal rank
@@ Property / cites work @@
+Improved online algorithms for parallel job scheduling and strip packing
+Normal rank
@@ Property / cites work @@
+A note on online strip packing
@@ Property / cites work: A note on online strip packing / rank @@
+Normal rank
@@ Property / cites work @@
+On Three-Dimensional Packing
@@ Property / cites work: On Three-Dimensional Packing / rank @@
+Normal rank
@@ Property / cites work @@
+Heuristic algorithms for on-line packing in three dimensions
+Normal rank
@@ Property / cites work @@
+Q2934715
@@ Property / cites work: Q2934715 / rank @@
+Normal rank
@@ Property / cites work @@
+A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing
+Normal rank
@@ Property / cites work @@
+The two-dimensional cutting stock problem revisited
+Normal rank
@@ Property / cites work @@
+Q5351886
@@ Property / cites work: Q5351886 / rank @@
+Normal rank
@@ Property / cites work @@
+On the two-dimensional knapsack problem
@@ Property / cites work: On the two-dimensional knapsack problem / rank @@
+Normal rank
@@ Property / cites work @@
+Maximizing the total profit of rectangles packed into a rectangle
+Normal rank
@@ Property / cites work @@
+Algorithm Theory - SWAT 2004
@@ Property / cites work: Algorithm Theory - SWAT 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+New Approximability Results for 2-Dimensional Packing Problems
+Normal rank
@@ Property / cites work @@
+A Polynomial Time Approximation Scheme for the Square Packing Problem
+Normal rank
@@ Property / cites work @@
+Faster approximation schemes for the two-dimensional knapsack problem
+Normal rank
@@ Property / cites work @@
+Algorithms and Computation
@@ Property / cites work: Algorithms and Computation / rank @@
+Normal rank
@@ Property / cites work @@
+A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for 3D Orthogonal Knapsack
+Normal rank
@@ Property / cites work @@
+Improved Bound for Online Square-into-Square Packing
+Normal rank
@@ Property / cites work @@
+Exact algorithms and APX-hardness results for geometric packing and covering problems
+Normal rank
@@ Property / cites work @@
+Packing anchored rectangles
@@ Property / cites work: Packing anchored rectangles / rank @@
+Normal rank
@@ Property / cites work @@
+A Breakthrough in Sphere Packing: The Search for Magic Functions
+Normal rank
@@ Property / cites work @@
+There is no asymptotic PTAS for two-dimensional vector packing
+Normal rank
@@ Property / cites work @@
+On Multidimensional Packing Problems
@@ Property / cites work: On Multidimensional Packing Problems / rank @@
+Normal rank
@@ Property / cites work @@
+New Algorithms for Bin Packing
@@ Property / cites work: New Algorithms for Bin Packing / rank @@
+Normal rank
@@ Property / cites work @@
+An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
+Normal rank
@@ Property / cites work @@
+Q5365101
@@ Property / cites work: Q5365101 / rank @@
+Normal rank
@@ Property / cites work @@
+Resource constrained scheduling as generalized bin packing
+Normal rank
@@ Property / cites work @@
+Q4291430
@@ Property / cites work: Q4291430 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4439452
@@ Property / cites work: Q4439452 / rank @@
+Normal rank
@@ Property / cites work @@
+Tight bounds for online vector bin packing
@@ Property / cites work: Tight bounds for online vector bin packing / rank @@
+Normal rank
@@ Property / cites work @@
+Q4763409
@@ Property / cites work: Q4763409 / rank @@
+Normal rank
@@ Property / cites work @@
+Packing Small Vectors
@@ Property / cites work: Packing Small Vectors / rank @@
+Normal rank
@@ Property / cites work @@
+Online Lower Bounds via Duality
@@ Property / cites work: Online Lower Bounds via Duality / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
+Normal rank
@@ Property / cites work @@
+Fast Approximation Algorithms for Knapsack Problems
+Normal rank
@@ Property / cites work @@
+Q4821303
@@ Property / cites work: Q4821303 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for knapsack problems with cardinality constraints
+Normal rank
@@ Property / cites work @@
+Parameterized Approximation Scheme for the Multiple Knapsack Problem
+Normal rank
@@ Property / cites work @@
+Book review of: A. Agnetis et al., Multiagent scheduling. Models and algorithms
+Normal rank
@@ Property / cites work @@
+Q3031924
@@ Property / cites work: Q3031924 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation schemes for scheduling on parallel machines
+Normal rank
@@ Property / cites work @@
+An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
+Normal rank
@@ Property / cites work @@
+Carathéodory bounds for integer cones
@@ Property / cites work: Carathéodory bounds for integer cones / rank @@
+Normal rank
@@ Property / cites work @@
+A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
+Normal rank
@@ Property / cites work @@
+Vector assignment problems: a general framework
@@ Property / cites work: Vector assignment problems: a general framework / rank @@
+Normal rank
@@ Property / cites work @@
+Vector assignment schemes for asymmetric settings
@@ Property / cites work: Vector assignment schemes for asymmetric settings / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating vector scheduling: almost matching upper and lower bounds
+Normal rank
@@ Property / cites work @@
+Bounds for Certain Multiprocessing Anomalies
@@ Property / cites work: Bounds for Certain Multiprocessing Anomalies / rank @@
+Normal rank
@@ Property / cites work @@
+New algorithms for an ancient scheduling problem.
@@ Property / cites work: New algorithms for an ancient scheduling problem. / rank @@
+Normal rank
@@ Property / cites work @@
+A better lower bound for on-line scheduling
@@ Property / cites work: A better lower bound for on-line scheduling / rank @@
+Normal rank
@@ Property / cites work @@
+Q4335203
@@ Property / cites work: Q4335203 / rank @@
+Normal rank
@@ Property / cites work @@
+Better Bounds for Online Scheduling
@@ Property / cites work: Better Bounds for Online Scheduling / rank @@
+Normal rank
@@ Property / cites work @@
+Q4952670
@@ Property / cites work: Q4952670 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2753936
@@ Property / cites work: Q2753936 / rank @@
+Normal rank
@@ Property / cites work @@
+On-line routing of virtual circuits with applications to load balancing and machine scheduling
+Normal rank
@@ Property / cites work @@
+Online Multidimensional Load Balancing
@@ Property / cites work: Online Multidimensional Load Balancing / rank @@
+Normal rank
@@ Property / cites work @@
+Tight Bounds for Online Vector Scheduling
@@ Property / cites work: Tight Bounds for Online Vector Scheduling / rank @@
+Normal rank
@@ Property / cites work @@
+On a dual version of the one-dimensional bin packing problem
+Normal rank
@@ Property / cites work @@
+Online algorithms for a dual version of bin packing
+Normal rank
@@ Property / cites work @@
+Q2707233
@@ Property / cites work: Q2707233 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2768348
@@ Property / cites work: Q2768348 / rank @@
+Normal rank
@@ Property / cites work @@
+Coordination Complexity of Parallel Price-Directive Decomposition
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of algorithms for dual bin packing problems
+Normal rank
@@ Property / cites work @@
+On-line and off-line approximation algorithms for vector covering problems
+Normal rank
@@ Property / cites work @@
+On some geometric methods in scheduling theory: A survey
+Normal rank