We study translational packing of convex polyhedra in three dimensions. Given $n$ convex polyhedra in $\mathbb{R}^3$, we seek a placement with pairwise disjoint interiors that minimizes the volume of an axis-parallel bounding box. Constant-factor approximation algorithms are known when rotations are allowed, but no approximation guarantee was previously known for arbitrary convex polyhedra with fixed orientations. A central difficulty is that, unlike in the plane, the total volume and the coordinate extents of the objects do not provide a useful lower bound on the optimum: even objects with small total volume and small diameter may require a container of large volume. We overcome this difficulty using a better geometric lower bound based on a surprising connection to Wang and Zahl's celebrated recent proof of the three-dimensional Kakeya conjecture. Using this, we obtain a polynomial-time $n^{o(1)}$-approximation algorithm. A recent strengthening of Wang and Zahl's theorem claimed by OpenAI gives a polylogarithmic approximation ratio for the same algorithm. Our ideas extend to bin and strip packing: for any fixed $δ>0$, we obtain the same approximation guarantees for translational packing of convex polyhedra whose coordinate widths are at most a $1-δ$ fraction of the corresponding container widths.
We consider the Euclidean Steiner Tree problem of connecting $n$ given points in $\mathbb{R}^d$ by a shortest network allowing the addition of Steiner points anywhere in the space. Arora [FOCS'96/'97, J. ACM'98] gave a polynomial-time approximation scheme (PTAS) for Euclidean Steiner Tree and TSP in every fixed dimension, and Trevisan [STOC'97, SICOMP'00] proved that Euclidean TSP is APX-hard in $O(\log n)$ dimensions. They left open whether Euclidean Steiner Tree admits a PTAS in high dimension. Our first contribution settles this thirty-year-old question by proving APX-hardness in $O(\log n)$ dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP $\not\subseteq $SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in $O(\log\log n)$ dimensions. This dimension bound is tight up to a factor of $O(\log\log\log n)$, since Arora's scheme is a PTAS in up to $\log\log n/\log\log\log n$ dimensions. In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time $2^{O_d(\varepsilon^{-(d-1)})}n\log n$ and proved matching Gap-ETH lower bounds for Euclidean TSP and Rectilinear Steiner Tree, but left a corresponding lower bound for Euclidean Steiner Tree as an open question. Our second contribution answers this question with a nearly tight lower bound on the dependence on accuracy for Euclidean Steiner Tree. However, given the recent claimed refutations of ETH and hence Gap-ETH by OpenAI and Anthropic, we use the weaker assumption that 3SAT has no truly subexponential-time algorithm, that is, no $2^{n^γ}$-time algorithm on formulas of size $n$ for any constant $γ<1$ (a hypothesis one might call weak ETH). Under this assumption, we prove that no $(1+\varepsilon)$-approximation algorithm runs in time $2^{O(\varepsilon^{-γ(d-1)})} poly(n)$ for any such $γ$.