The Volume of a Crosspolytope Truncated by a Halfspace
The Volume of a Crosspolytope Truncated by a Halfspace
复制标题
DOI：
10.1007/978-3-030-14812-6_2
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Ei Ando;Shoichi Tsuchiya
中科院分区：
文献类型：
--
作者：
Ei Ando;Shoichi Tsuchiya
在本文中，我们考虑计算被半空间截断的任意维交叉多胞体的体积。由于交叉多面体具有指数级多面，因此我们无法通过将截断的交叉多面体划分为单纯形来有效地计算体积。我们展示了计算体积的反时间算法。这与 0−1 背包多胞体形成对比，其体积难以计算。本文对截断交叉多胞体体积的计算感兴趣，因为我们推测以下问题可能有肯定的答案：用于计算多胞体体积的多项式时间算法的存在是否与 K 的几何对偶相同？我们举一个例子，答案是肯定的。
In this paper, we consider the computation of the volume of ann-dimensional crosspolytope truncated by a halfspace. Since a crosspolytope has exponentially many facets, we cannot efficiently compute the volume by dividing the truncated crosspolytope into simplices. We show antime algorithm for the computation of the volume. This makes a contrast to the 0−1 knapsack polytope, whose volume is-hard to compute. The paper is interested in the computation of the volume of the truncated crosspolytope because we conjecture the following question may have an affirmative answer: Does the existence of a polynomial time algorithm for the computation of the volume of a polytopeKimply the same forK’s geometric dual? We give one example where the answer is yes.