1BP: FPTAS for config LP

Dependencies:

1. Bin packing and Knapsack
2. Bin packing: configuration LP
3. BP: α(1+ε)-approx solution to config LP using α-approx algorithm for knapsack
4. FPTAS for 1D knapsack

$\newcommand{\eps}{\varepsilon}$ $\newcommand{\Otild}{\widetilde{O}}$ $\newcommand{\Sum}{\operatorname{sum}}$ $\newcommand{\lin}{\operatorname{lin}}$ Let $I$ be a 1BP instance containing $n$ items. Then we can obtain a feasible solution $x$ to the configuration LP of $I$, such that $\Sum(x) \le (1+\eps)\lin(I)$. Moreover, we can do this in time \[ O\left(\frac{n^5}{\eps^4}\log\left(\frac{n}{\eps}\right)^3\right). \]

Proof follows directly from the dependencies.

Dependency for:

1. 1BP: Karmarkar-Karp algorithm (broken)

Info:

• Depth: 5
• Number of transitive dependencies: 13

Transitive dependencies:

1. /optimization/lin-func-is-max-at-extreme-point-of-polytope
2. /bounds/upper-exp-bound
3. Bin packing and Knapsack
4. Pseudo-polynomial time algorithm for 1D knapsack
5. FPTAS for 1D knapsack
6. Bin packing: configuration LP
7. Group
8. Ring
9. Semiring
10. Matrix
11. Bound on log
12. Approximation algorithm for covering LPs
13. BP: α(1+ε)-approx solution to config LP using α-approx algorithm for knapsack