Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
From MaRDI portal
Publication:3893333
DOI10.1137/0209062zbMath0447.68079OpenAlexW1997959089MaRDI QIDQ3893333
Michael R. Garey, David S. Johnson, Edward G. jun. Coffman, Robert Endre Tarjan
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209062
Combinatorial aspects of packing and covering (05B40) Discrete mathematics in relation to computer science (68R99)
Related Items
A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing, Tight approximation algorithms for geometric bin packing with skewed items, Peak demand minimization via sliced strip packing, An improved approximation algorithm for scheduling monotonic moldable tasks, High multiplicity strip packing with three rectangle types, An improved approximation for packing big two-bar charts, A Tight (3/2+ε) Approximation for Skewed Strip Packing., Complexity and inapproximability results for parallel task scheduling and strip packing, Unnamed Item, Asynchronous optimization of part logistics routing problem, Rectangle packing with one-dimensional resource augmentation, Multiple-type, two-dimensional bin packing problems: Applications and algorithms, A hybrid heuristic algorithm for the 2D variable-sized bin packing problem, A block-based layer building approach for the 2D guillotine strip packing problem, Coordination Mechanisms for Selfish Parallel Jobs Scheduling, Strip packing with precedence constraints and strip packing with release times, Approximate strip packing: revisited, A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints, A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem, On two dimensional packing, APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS, Tighter Bounds for the Gap and Non-IRUP Constructions in the One-dimensional Cutting Stock Problem, Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints, The nesting problem in the leather manufacturing industry, A new lower bound for online strip packing, Bin packing with divisible item sizes, Resource sharing combined with layout effects in high-level synthesis, Polynomial-time approximation schemes for circle and other packing problems, Approximate composable truthful mechanism design, Efficient heuristics for robot acquisition planning for a CIM system, Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem, Approximation and online algorithms for multidimensional bin packing: a survey, Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem, Two- and three-dimensional parametric packing, iGreen: green scheduling for peak demand minimization, Scheduling parallel jobs to minimize the makespan, An approximation scheme for strip packing of rectangles with bounded dimensions, Guillotineable bin packing: A genetic approach, Triple-solution approach for the strip packing problem with two-staged patterns, Approximation Algorithms for Scheduling with Resource and Precedence Constraints, A \((5/3+\varepsilon)\)-approximation for strip packing, Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle, A 2.5 times optimal algorithm for packing in two dimensions, Dynamic multi-dimensional bin packing, A comparison of heuristic algorithms for cost-oriented assembly line balancing, Improved upper bounds for online malleable job scheduling, On contiguous and non-contiguous parallel task scheduling, A Polynomial Time Approximation Scheme for the Square Packing Problem, An improved BL lower bound, Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming, Unnamed Item, Parametric on-line algorithms for packing rectangles and boxes., Packing Rectangles into 2OPT Bins Using Rotations, Exact algorithms for the guillotine strip cutting/packing problem., The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers, An approximation scheme for the two-stage, two-dimensional knapsack problem, Co-scheduling algorithms for high-throughput workload execution, An effective approximation algorithm for the malleable parallel task scheduling problem, Absolute approximation ratios for packing rectangles into bins, Offline first-fit decreasing height scheduling of power loads, Prices of Anarchy of Selfish 2D Bin Packing Games, Packing, covering and tiling in two-dimensional spaces, Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, Online square packing with gravity, Asymptotically optimal scheduling of random malleable demands in smart grid, Relations between capacity utilization, minimal bin size and bin number, Two-dimensional bin packing with one-dimensional resource augmentation, Oriented aligned rectangle packing problem, On-line scheduling of parallel jobs in a list, New upper bounds for online strip packing, Exact algorithms for the two-dimensional guillotine knapsack, Recent advances on two-dimensional bin packing problems, Packings in two dimensions: Asymptotic average-case analysis of algorithms, A new upper bound for the online square packing problem in a strip, The two-dimensional cutting stock problem revisited, Average-case performance analysis of a 2D strip packing algorithm -- NFDH, Improved approximation for two dimensional strip packing with polynomial bounded width, Greed in resource scheduling, Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem, Average-case analysis of cutting and packing in two dimensions, Heuristics for packing semifluids, The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio, Upper bounds for heuristic approaches to the strip packing problem, Upper Bounds for Heuristic Approaches to the Strip Packing Problem, Closing the Gap for Pseudo-Polynomial Strip Packing, Two-bar charts packing problem, A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem, Three-dimensional packings with rotations, Malleable scheduling for flows of jobs and applications to MapReduce, Analysis of a first-fit algorithm for the capacitated unit covering problem, A note on online strip packing, A note on the Kenyon-Remila strip-packing algorithm, Probabilistic analysis of shelf algorithms for strip packing, Approximate algorithms to pack rectangles into several strips, Two Dimensional Knapsack with Unloading Constraints, Selfish Square Packing, Techniques and results on approximation algorithms for packing circles, New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, Guillotine cutting is asymptotically optimal for packing consecutive squares, Two-dimensional packing problems: a survey, Network flows and non-guillotine cutting patterns, An algorithm for the 2D guillotine cutting stock problem, Two-dimensional packing algorithms for layout of disconnected graphs, Resource augmentation in two-dimensional packing with orthogonal rotations, Scheduling space-sharing for internet advertising, Strip based compact formulation for two-dimensional guillotine cutting problems, Performance testing of rectangular parts-nesting heuristics, On Packing Two-Dimensional Bins, New approximability results for two-dimensional bin packing
