Sep, 2008

高维几何物体的并集和交集体积近似

PDF
TL;DR本研究探讨高维几何对象的求并集体积问题。本文给出了一个快速的 FPRAS 算法，可以有效地逼近 Klee's measure problem 和 hypervolume indicator，并能够逼近由弱成员资格证明给出的凸体的并集体积。同时，作者还探讨了高维几何对象的交集计算问题，并证明了其 #P 难度。
high-dimensional geometric objectsfprasklee's measure problemhypervolume indicatorconvex bodies
发现论文，激发创造
  • 用于估算凸体积的量子算法

    本研究提出一种基于 Chebyshev cooling 并利用量子随机游走技术的量子算法，用于估算多维凸包的体积，比已知的经典算法要更快，同时还证明了量子算法所需的查询次数。

    Aug, 2019

  • 寻找 $n$ 个点中最大的空轴对齐盒子

    该研究给出了在超立方体中包含 n 个点的内部空置轴平行盒子的最大体积的上下界，并利用该界设计了一种高效的近似算法，该算法的运行时间与维度成对数增长，同时还给出了一个空置超立方体的最大体积估计。

    Sep, 2009

  • 体积和高斯体积的高斯冷却和 O*(n^3) 算法

    我们提出了一种基于随机化算法的方法，用于估计具有会员 Oracle 的圆满凸体的体积。我们还提供了一种有改进的高斯分布采样算法，并分析了采样复杂性。

    Sep, 2014

  • 论最大体积单纯形和子行列式

    本论文提出了一种多项式时间复杂度下可以近似求解凸包中体积最大值的算法，近似比可以达到 $O (log d)^{d/2}$。此外，本文也展示了此问题的不可近似性，除非 $P=NP$。类似的结果也适用于矩阵行列式的最大值问题。

    Jun, 2014

  • 通过在 Wasserstein 空间中的多面体优化实现均场变分推断的算法

    有限维多面体子集、Wasserstein 空间、均场变分推断、最小化算法和 KL 散度。

    Dec, 2023

  • 计算高斯体积的三次算法

    本研究提出了应用于凸集内标准高斯分布抽样及高斯度量估计的随机算法，并证明它们在一般性成员查询模型下的可行性，其采样的时间复杂度为每个样本均摊 $O^*(n^2)$，比现有最先进算法快 $n$ 倍。在等周问题、平滑退火、避免变换到各向同性和快速随机行走等方面实现了改进。

    Jun, 2013

  • 学习半空间交集的改进难度结果

    通过与半空间和所谓的并行煎饼分布的新颖联系，我们以统一的方式获得了较强（而且令人惊讶地简单）的在不适当的情况下学习半空间交集的下界，这是过去几年强大的高维统计学中许多下界构造的核心，我们还给出了统计查询框架下的无条件难度结果。

    Feb, 2024

  • 计算超体积指标的箱形分解算法

    提出了一种利用轴对齐超矩形进行支配区域划分的新方法来计算超体积指标，包括一个非增量算法和一个增量算法。虽然其理论复杂度受到了分区复杂度的下界限制，但该方法在实践中具有高效性。此外，证明了 WFG 算法的最坏情况下的复杂度的改进上限和下限。

    Oct, 2015

  • 随机超平面镶嵌的降维

    研究了如何利用随机超平面对区域进行均匀的镶嵌，并利用超平面将欧氏空间中的有界集嵌入哈明空间中，从而实现对欧氏空间中集合的离散化降维。

    Nov, 2011

  • 一种更快的切平面方法及其对组合优化和凸优化的影响

    通过使用标准约减和新技术的混合方法，我们改进了查找凸集中点的运行时间，同时提高了在连续和组合优化中的算法性能，特别是子模规划和半定规划问题。

    Aug, 2015