Certificate and Scope

Lower-Bound Certificate

Total size gives a lower bound on how many capacity-one bins any packing needs.

highlighted = computed this step

Add sizes

The total item size is 2.

1/2+1/2+1/3+1/3+1/3=21/2 + 1/2 + 1/3 + 1/3 + 1/3 = 2
Certificate and scopeThe chart pairs the packing with the exact lower bound.lower-bound certificatesorted orderA=1/2B=1/2C=1/3D=1/3E=1/3Bin 1A 1/2B 1/2fill 1left 0Bin 2C 1/3D 1/3E 1/3fill 1left 0certificatetotal size2capacity1lower bound2bins used2optimal for this instance

Capacity bound

Each bin holds at most 1, so the lower bound is total size divided by capacity, rounded up.

⌈2/1⌉\left\lceil 2 / 1\right\rceil
Certificate and scopeThe chart pairs the packing with the exact lower bound.lower-bound certificatesorted orderA=1/2B=1/2C=1/3D=1/3E=1/3Bin 1A 1/2B 1/2fill 1left 0Bin 2C 1/3D 1/3E 1/3fill 1left 0certificatetotal size2capacity1lower bound2bins used2optimal for this instance

Lower bound

The lower bound is 2 bins.

lower bound=2\text{lower bound}=2
Certificate and scopeThe chart pairs the packing with the exact lower bound.lower-bound certificatesorted orderA=1/2B=1/2C=1/3D=1/3E=1/3Bin 1A 1/2B 1/2fill 1left 0Bin 2C 1/3D 1/3E 1/3fill 1left 0certificatetotal size2capacity1lower bound2bins used2optimal for this instance

Matches packing

FFD used 2 bins, exactly matching the lower bound.

bins used=lower bound=2\text{bins used}=\text{lower bound}=2
Certificate and scopeThe chart pairs the packing with the exact lower bound.lower-bound certificatesorted orderA=1/2B=1/2C=1/3D=1/3E=1/3Bin 1A 1/2B 1/2fill 1left 0Bin 2C 1/3D 1/3E 1/3fill 1left 0certificatetotal size2capacity1lower bound2bins used2optimal for this instance