An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution

作者：Ando Ei^*; Kijima Shuji

来源：Algorithmica, 2016, 76(4): 1245-1263.

DOI：10.1007/s00453-015-0096-5

• Approximate convolution
• Volume computation
• #P-hard
• Knapsack polytope

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 the volume computation of 0-1 knapsack polytopes, which is known to be #P-hard. This paper presents a new technique based on approximate convolutions for a deterministic approximation 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.

• 出版日期2016-12