Approximation algorithms for orthogonal packing problems for hypercubes

DOI10.1016/j.tcs.2009.07.030zbMath1187.68708OpenAlexW1976115962MaRDI QIDQ1035685

Rolf Harren

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.030

zbMATH Keywords

hypercube packingsquare packingorthogonal knapsack problem

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (7)

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Packing Cubes into a Cube in (D>3)-Dimensions ⋮ 2D knapsack: packing squares ⋮ On the weak computability of a four dimensional orthogonal packing and time scheduling problem ⋮ 2D Knapsack: Packing Squares ⋮ Online square-into-square packing ⋮ Packing cubes into a cube is NP-complete in the strong sense

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing the total profit of rectangles packed into a rectangle
• Bin packing can be solved within 1+epsilon in linear time
• On the two-dimensional knapsack problem
• Approximating the advertisement placement problem
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
• A Polynomial Time Approximation Scheme for the Square Packing Problem
• New Approximability Results for 2-Dimensional Packing Problems
• On strip packing With rotations
• An asymptotic approximation algorithm for 3D-strip packing
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Approximating the Orthogonal Knapsack Problem for Hypercubes
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Algorithm Theory - SWAT 2004
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Approximation Algorithms for 3D Orthogonal Knapsack
• Mathematical Foundations of Computer Science 2005
• On packing of squares and cubes
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• Algorithms and Computation
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Approximation algorithms for orthogonal packing problems for hypercubes