##### Document Text Contents

Page 1

AD-AO85 315 ILLINOIS UiIV AT

URBANA-CHAMPAIGN APPLIED COMPUTATION-ETC

F/G 12/1

ALOWER BOUND FOR ON-LINE ONE-DIMENSIONAL

BIN PACKCING ALGORITHM--ETC(U)

DEC 79 D J BROWN N0001-79-C-0o24

UNCLASSIFIED ACT-19 NL

F fllfllfllfllfllfllIN

Page 2

.:~iCO*OI TED SCIENCE LAO*AMOY

APPLIED COMPUTA TION TH7EORY OROU

A LOWER BOUND L

LINE

-. ~%PIERfTY OF ILUNOI0 -~ URBANA, IL L(NOIS1

Page 12

8

114 1 1 3 10 fI 'A an m2 0 i2I 2 + 3 < and m2 + 0

2 if I m<2 + m3 < and m 2 # 0, m = 0

3 1 and in 3i 2 0.

iiLetting lcil (I oil ) represent the number of bins in ai (0i), we have

A(L1 ) = 1a1 + 1511

A(L 1 L2 ) = Ial + Ioll + IY21 + 1021 (2.2)

A(L I L2 L3 ) = Iall + loll + 1I21 + 1 21 + I3I + 1031

1

Notice that no two pieces of size - + e will fit in the same bin, nor2

will any of the n pieces of size T + e fit in an , a2' or a bin, so

A(L) 2 n + I1 1 +12I +aI3 (2.3)

Let us assume that

maxfrl(n), r 2 (n), r 3 (n), r 4 (n)j < 10-9 (2.4)1 2 3 471

Combining equations (2.1), (2.2), and (2.3), this tells us

n 109 1 ,1 + ll

42 71 Il

n 109 l7 _ 1 + Ill + 2 + 1021

n2 109 • + I1 o + + 1021 + 1131 + 131(2.5)

109 > V

1 I1 + 1C21 + I + n

Because there are n pieces of size 42 3e, of size - + s, and n of

size - + e,

I

Page 13

9

b w 9 B

n m2 (2.6)

b LB

w

From (2.6), we immnediately have

4 4 '

42 4 2 I

b LB

- 2nm

(2.7)

2 b B

w

Summuing equations (2.5) and (2.7),

109 1 1 14 1+1

Sn(~ + + -1+ 1) - n (Z" + 1+)

;P 41 ot 1 + 310 1 + 31c~ + 21 021 + 2Ia3I + 1031 + n (2.8)

Z-- 'B2 - L

3

Simplifying inequality (2.8) and rearranging terms:

Page 24

20

(i) Assume that j 5 t-2. Then

"je l 1(3.23)-a t-i+l 2

i.=2 a

Multiplying both sides of (3.23) by j +2 and then applying the Lemma,

j+l

Ia-- mt-+ 1 < 1+2 (3.24)

For j 2 2, j+2 j and the result is proved. For j =1, (3.24) reduces

2

to t Y-. Since mt.I is an integer, this says mt.I 1 1 and once again

the desired result holds.

(ii) Assume that j = t-1; i.e., b Ci Similar to inequality (3.21),

we have

1 mm + <-- + 1 (3.25)

1 2 mt-i+a

t i=2 i t

Multiplying both sides of (3.25) by t and applying the Lemma,

t i m<t + t-mr ~ < " + a

12a -I1 t-i+l 2 a

For t 2 3,

t t-2

a t 2

and so

ia2aihl mt'+mipod.

L ~ and the theorem is proved.

Page 25

21

References

[i] B. S. Baker, D. J. Brown, and H. P. Katseff, "A 5/4 algorithm for

two-dimensional bin packing," in preparation.

(2] B. S. Baker, E. G. Coffman, and R. L. Rivest, "Orthogonal packings

in two dimensions," SIAM Journal of Computing, to appear.

[3] B. S. Baker and J. S. Schwartz, "Shelf algorithms for two-dimensional

packing problems," Proceedings 1979 CISS, Johns Hopkins University,

Baltimore, Maryland.

[4] D. J. Brown, work in progress.

[5] D. J. Brown, "An improved BL lower bound," submitted for publication

(1979).

[6] D. J. Brown, B. S. Baker, and H. P. Katseff, "Lower bounds for on-

line two-dimensional packing algorithms," technical report,

Coordinated Science Laboratory, University of Illinois.

[7] E. G. Coffman, M. R. Garey, D. S. Johnson, and R. E. Tarjan,

"Performance bounds for level-oriented two dimensional packing

algorithms," Technical Memorandum, Bell Laboratories, Murray Hill,

N.J.

[8] M. R. Garey and D. S. Johnson, Computers and Intractability: A

Guide to the Theory of NP-Completeness, W. H. Freeman & Co., San

Francisco, CA, 1979.

[91 1. Golan, "Performance bounds for orthogonal oriented two-dimensional

packing algorithms," draft (1979).

[10) S. W. Golomb, "On certain nonlinear recurring sequences," American

Mathematical Monthly, vol. 70, pp. 403-405, 1963.

[111 S. W. Golomb, "On the sum of the reciprocals of the Fermat numbers and

related irrationalities," Canadian Journal of Mathematics, vol. 15,

pp. 475-478, 1963.

[121 D. S. Johnson, "Near optimal bin packing algorithms," Ph.D. Dissertation,

Massachusetts Institute of Technology, Cambridge, Mass., June 1973.

[13] D. S. Johnson, "Fast algorithms for bin packing,"J. Comput. System Sci.,

vol. 8, pp. 272-314, 1974.

[141 D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham,

"Worst-case performance bounds for simple one-dimensional packing

algorithms," SIAM Journal of Computing, vol. 3, pp. 299-325, 1974.

[15] J. A. Storer, "An improved lower bound for on-line packing with

decreasing width," draft (1979).

[16] A. Yao, "New algorithms for bin packing," Report No. STAN-CS-78-662,

Computer Science Department, Stanford University, Stanford, CA, 1978.

L,

AD-AO85 315 ILLINOIS UiIV AT

URBANA-CHAMPAIGN APPLIED COMPUTATION-ETC

F/G 12/1

ALOWER BOUND FOR ON-LINE ONE-DIMENSIONAL

BIN PACKCING ALGORITHM--ETC(U)

DEC 79 D J BROWN N0001-79-C-0o24

UNCLASSIFIED ACT-19 NL

F fllfllfllfllfllfllIN

Page 2

.:~iCO*OI TED SCIENCE LAO*AMOY

APPLIED COMPUTA TION TH7EORY OROU

A LOWER BOUND L

LINE

-. ~%PIERfTY OF ILUNOI0 -~ URBANA, IL L(NOIS1

Page 12

8

114 1 1 3 10 fI 'A an m2 0 i2I 2 + 3 < and m2 + 0

2 if I m<2 + m3 < and m 2 # 0, m = 0

3 1 and in 3i 2 0.

iiLetting lcil (I oil ) represent the number of bins in ai (0i), we have

A(L1 ) = 1a1 + 1511

A(L 1 L2 ) = Ial + Ioll + IY21 + 1021 (2.2)

A(L I L2 L3 ) = Iall + loll + 1I21 + 1 21 + I3I + 1031

1

Notice that no two pieces of size - + e will fit in the same bin, nor2

will any of the n pieces of size T + e fit in an , a2' or a bin, so

A(L) 2 n + I1 1 +12I +aI3 (2.3)

Let us assume that

maxfrl(n), r 2 (n), r 3 (n), r 4 (n)j < 10-9 (2.4)1 2 3 471

Combining equations (2.1), (2.2), and (2.3), this tells us

n 109 1 ,1 + ll

42 71 Il

n 109 l7 _ 1 + Ill + 2 + 1021

n2 109 • + I1 o + + 1021 + 1131 + 131(2.5)

109 > V

1 I1 + 1C21 + I + n

Because there are n pieces of size 42 3e, of size - + s, and n of

size - + e,

I

Page 13

9

b w 9 B

n m2 (2.6)

b LB

w

From (2.6), we immnediately have

4 4 '

42 4 2 I

b LB

- 2nm

(2.7)

2 b B

w

Summuing equations (2.5) and (2.7),

109 1 1 14 1+1

Sn(~ + + -1+ 1) - n (Z" + 1+)

;P 41 ot 1 + 310 1 + 31c~ + 21 021 + 2Ia3I + 1031 + n (2.8)

Z-- 'B2 - L

3

Simplifying inequality (2.8) and rearranging terms:

Page 24

20

(i) Assume that j 5 t-2. Then

"je l 1(3.23)-a t-i+l 2

i.=2 a

Multiplying both sides of (3.23) by j +2 and then applying the Lemma,

j+l

Ia-- mt-+ 1 < 1+2 (3.24)

For j 2 2, j+2 j and the result is proved. For j =1, (3.24) reduces

2

to t Y-. Since mt.I is an integer, this says mt.I 1 1 and once again

the desired result holds.

(ii) Assume that j = t-1; i.e., b Ci Similar to inequality (3.21),

we have

1 mm + <-- + 1 (3.25)

1 2 mt-i+a

t i=2 i t

Multiplying both sides of (3.25) by t and applying the Lemma,

t i m<t + t-mr ~ < " + a

12a -I1 t-i+l 2 a

For t 2 3,

t t-2

a t 2

and so

ia2aihl mt'+mipod.

L ~ and the theorem is proved.

Page 25

21

References

[i] B. S. Baker, D. J. Brown, and H. P. Katseff, "A 5/4 algorithm for

two-dimensional bin packing," in preparation.

(2] B. S. Baker, E. G. Coffman, and R. L. Rivest, "Orthogonal packings

in two dimensions," SIAM Journal of Computing, to appear.

[3] B. S. Baker and J. S. Schwartz, "Shelf algorithms for two-dimensional

packing problems," Proceedings 1979 CISS, Johns Hopkins University,

Baltimore, Maryland.

[4] D. J. Brown, work in progress.

[5] D. J. Brown, "An improved BL lower bound," submitted for publication

(1979).

[6] D. J. Brown, B. S. Baker, and H. P. Katseff, "Lower bounds for on-

line two-dimensional packing algorithms," technical report,

Coordinated Science Laboratory, University of Illinois.

[7] E. G. Coffman, M. R. Garey, D. S. Johnson, and R. E. Tarjan,

"Performance bounds for level-oriented two dimensional packing

algorithms," Technical Memorandum, Bell Laboratories, Murray Hill,

N.J.

[8] M. R. Garey and D. S. Johnson, Computers and Intractability: A

Guide to the Theory of NP-Completeness, W. H. Freeman & Co., San

Francisco, CA, 1979.

[91 1. Golan, "Performance bounds for orthogonal oriented two-dimensional

packing algorithms," draft (1979).

[10) S. W. Golomb, "On certain nonlinear recurring sequences," American

Mathematical Monthly, vol. 70, pp. 403-405, 1963.

[111 S. W. Golomb, "On the sum of the reciprocals of the Fermat numbers and

related irrationalities," Canadian Journal of Mathematics, vol. 15,

pp. 475-478, 1963.

[121 D. S. Johnson, "Near optimal bin packing algorithms," Ph.D. Dissertation,

Massachusetts Institute of Technology, Cambridge, Mass., June 1973.

[13] D. S. Johnson, "Fast algorithms for bin packing,"J. Comput. System Sci.,

vol. 8, pp. 272-314, 1974.

[141 D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham,

"Worst-case performance bounds for simple one-dimensional packing

algorithms," SIAM Journal of Computing, vol. 3, pp. 299-325, 1974.

[15] J. A. Storer, "An improved lower bound for on-line packing with

decreasing width," draft (1979).

[16] A. Yao, "New algorithms for bin packing," Report No. STAN-CS-78-662,

Computer Science Department, Stanford University, Stanford, CA, 1978.

L,