2D BP: APTAS for config LP

Dependencies:

$\newcommand{\eps}{\varepsilon}$ $\newcommand{\Th}{^{\textrm{th}}}$ $\newcommand{\opt}{\operatorname{opt}}$ $\newcommand{\rvol}{\operatorname{rvol}}$ $\newcommand{\defeq}{:=}$ Let $I$ be a 2D geometric bin packing instance with $n$ items such that there are $m$ types of items, and all items of the same type are identical. Let $b_i$ be the number of items of type $i$. Let $A$ be the configuration matrix of $I$.

Let $v^*$ be the optimal objective value of the configuration LP. Then for any $\eps > 0$, we can obtain in polynomial time a feasible solution to the configuration LP of objective value at most $(1+\eps)v^* + 4$.

Proof

Let $g = \rvol$ and $\lambda = 4$. Let $P$ be the NFDH algorithm and $Q$ be a PTAS for density-restricted 2D geometric knapsack. For any $X \subseteq I$, if $\rvol(I) \le 1/\lambda = 1/4$, then $P$ can pack $X$ into at most $c = 2$ bins. Then the $(g, \lambda)$-density-restricted configuration LP of $I$ can be approximately solved in polynomial time using $P$ and $Q$. We can then use NFDH to remove the density restriction.

Dependency for: None

Info:

Depth: 6
Number of transitive dependencies: 20

Transitive dependencies:

/optimization/lin-func-is-max-at-extreme-point-of-polytope
/bounds/upper-exp-bound
Bin packing and Knapsack
Geometric packing problems (BP, KS, SP) and rvol
NFDH algorithm
NFDH: area of adjacent bins
2D BP: NFDH for small items
PTAS for 2D geometric density-restricted knapsack
Bin packing: configuration LP
Bin packing: density-restricted config LP
Bin packing: removing density restriction from config LP
Group
Ring
Semiring
Matrix
Stacking
Product of stacked matrices
Bound on log
Approximation algorithm for covering LPs
BP: α(1+ε)-approx solution to density-restricted config LP using α-approx algorithm for density-restricted knapsack