An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution
An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution
复制标题
DOI：
10.1007/s00453-015-0096-5
复制
发表时间：
2016-12
期刊：
影响因子：
1.1
通讯作者：
Ei Ando;S. Kijima
中科院分区：
文献类型：
--
作者：
Ei Ando;S. Kijima
计算高维体积是一个困难的问题，即使是近似。在过去的三十年中，已经发展了一些用于解决#P-hard问题的随机逼近技术，而一些确定性逼近算法仅针对少数#P-hard问题。受一种新的确定性逼近方法的启发，本文研究了0- 1背包多面体的体积计算问题，这类多面体是P-困难的。本文提出了一种新的基于近似卷积的体积计算的确定性近似方法，并给出了0-1背包多面体体积计算的完全多项式时间近似方案。我们还给出了一个扩展的结果，多约束背包多面体与一个常数的限制。
Computing high dimensional volumes is a hard problem, even for approximation. Several randomized approximation techniques for #P-hard problems have been developed in the three decades, while some deterministic approximation algorithms are recently developed only for a few #P-hard problems. Motivated by a new technique for a deterministic approximation, this paper is concerned with thevolumecomputation of 0-1knapsack polytopes, which is known to be #P-hard. This paper presents a new technique based onapproximate convolutionsfor adeterministicapproximation of volume computations, and provides a fully polynomial-time approximation scheme for the volume computation of 0-1 knapsack polytopes. We also give an extension of the result to multi-constrained knapsack polytopes with a constant number of constraints.