跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+0已有论文修订
+92新增 AI 导读

arXiv 最近完成扫描:2026-11-23 01:07 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

统计 2026-11-22 04:15 — 2026-11-23 04:15(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-23 01:07最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-23 01:05(北京时间)
新论文 · v1arXiv:2611.26352

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

Polylogarithmic Approximation for Packing Convex Polyhedra

Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae

AI 速读 基于摘要

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

cs.CG · cs.DS

查看原文摘要

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.

新论文 · v1arXiv:2611.24611

Inapproximability of Euclidean Steiner Tree

Simon Bartlmae

原文摘要

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 $γ$.

cs.CG · cs.DS