1BP: ⌈size(I)⌉ ≤ opt(I)

Dependencies:

1. Bin packing and Knapsack

$\newcommand{\Size}{\operatorname{size}}$ $\newcommand{\Sum}{\operatorname{sum}}$ $\newcommand{\opt}{\operatorname{opt}}$ $\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}$ Let $I$ be a 1BP instance. Then $\ceil{\Size(I)} \le \opt(I)$.

Proof

Let $m = \opt(I)$. Let $B_i$ be the items in the $i^{\textrm{th}}$ bin in the optimal packing. Then $\Size(B_i) \le 1$ and \[ \ceil{\Size(I)} = \ceil{\sum_{i=1}^m \Size(B_i)} \le \ceil{\sum_{i=1}^m 1} = m = \opt(I). \]

Dependency for:

1. 1BP: APTAS
2. 1BP: NextFit(S) ≤ ⌈2size(S)⌉
3. 1BP: Karmarkar-Karp algorithm (broken)
4. 1BP: NextFit(I) ≤ ⌈size(I)/(1-ε)⌉ for ε-small items

Info:

• Depth: 1
• Number of transitive dependencies: 1

Transitive dependencies:

1. Bin packing and Knapsack