RAIRO - Theoretical Informatics and Applications · 1988 · 83 citations · 6 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationApproximation AlgorithmsCombinatorial OptimizationGeometric OptimizationBin PackingBin Packing ProblemDynamic Storage AllocationPackingPacking ProblemsPolynomial Time ComplexityPolynomial-time AlgorithmsStorage Allocation
We consider the problem of packing rectangles of height 1 when the x-coordinates of their left and right edges are specified. In the off-line case the optimal solution can be trivially found in polynomial time. In the on-line case no algorithm can have performance ratio better than 3. A connection between this problem and dynamic storage allocation is shown.
6
E. G. Coffman, M. R. Garey, David S. Johnson · SIAM Journal on Computing · 1983 · 167 citations
A algorithm for two-dimensional packing
Brenda S. Baker, Donna J. Brown, Howard P. Katseff · Journal of Algorithms · 1981 · 154 citations
Lower bounds for on-line two-dimensional packing algorithms
D. Brown, BrendaS. Baker, H.P. Katseff · Acta Informatica · 1982 · 59 citations