跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.26352 · v1

Polylogarithmic Approximation for Packing Convex Polyhedra

凸多面体装箱问题的多对数近似算法

首次提交 2026-11-20 00:24
版本更新 2026-11-20 00:24
雷达观测 2026-11-20 12:52
arXiv ↗PDF ↗

摘要

We study translational packing of convex polyhedra in three dimensions. Given nn convex polyhedra in R3\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 no(1)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δ>0, we obtain the same approximation guarantees for translational packing of convex polyhedra whose coordinate widths are at most a 1−δ1-δ fraction of the corresponding container widths.

作者备注:28 pages, 8 figures

AI 论文解读

基于摘要 · 非全文审阅

针对固定方向的凸多面体三维平移装箱问题,利用与Kakeya猜想的联系,作者报告了多项式时间的n^{o(1)}近似算法,并在更强定理下达到多对数近似比。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-20 00:24 · 最新观测版本

Polylogarithmic Approximation for Packing Convex Polyhedra

We study translational packing of convex polyhedra in three dimensions. Given nn convex polyhedra in R3\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 no(1)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δ>0, we obtain the same approximation guarantees for translational packing of convex polyhedra whose coordinate widths are at most a 1−δ1-δ fraction of the corresponding container widths.

查看此版本解读 →查看此版本原文 ↗