TY - CHAP
T1 - An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution Integral
AU - Ando, Ei
AU - Kijima, Shuji
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - Computing high dimensional volumes is a hard problem, even for approximation. It is known that no polynomial-time deterministic algorithm can approximate with ratio 1.999n the volumes of convex bodies in the n dimension as given by membership oracles. Several randomized approximation techniques for #P-hard problems has been developed in the three decades, while some deterministic approximation algorithms are recently developed only for a few #P-hard problems. For instance, Stefankovic, Vempala and Vigoda (2012) gave an FPTAS for counting 0-1 knapsack solutions (i.e., integer points in a 0-1 knapsack polytope) based on an ingenious dynamic programming. Motivated by a new technique for designing FPTAS for #P-hard problems, this paper is concerned with the volume computation of 0-1 knapsack polytopes: it is given by {x (Formula presented.)} with a positive integer vector a and a positive integer b as an input, the volume computation of which is known to be #P-hard. Li and Shi (2014) gave an FPTAS for the problem by modifying the dynamic programming for counting solutions. This paper presents a new technique based on approximate convolution integral for a deterministic approximation of volume computations, and provides an FPTAS for the volume computation of 0-1 knapsack polytopes.
AB - Computing high dimensional volumes is a hard problem, even for approximation. It is known that no polynomial-time deterministic algorithm can approximate with ratio 1.999n the volumes of convex bodies in the n dimension as given by membership oracles. Several randomized approximation techniques for #P-hard problems has been developed in the three decades, while some deterministic approximation algorithms are recently developed only for a few #P-hard problems. For instance, Stefankovic, Vempala and Vigoda (2012) gave an FPTAS for counting 0-1 knapsack solutions (i.e., integer points in a 0-1 knapsack polytope) based on an ingenious dynamic programming. Motivated by a new technique for designing FPTAS for #P-hard problems, this paper is concerned with the volume computation of 0-1 knapsack polytopes: it is given by {x (Formula presented.)} with a positive integer vector a and a positive integer b as an input, the volume computation of which is known to be #P-hard. Li and Shi (2014) gave an FPTAS for the problem by modifying the dynamic programming for counting solutions. This paper presents a new technique based on approximate convolution integral for a deterministic approximation of volume computations, and provides an FPTAS for the volume computation of 0-1 knapsack polytopes.
UR - http://www.scopus.com/inward/record.url?scp=84921628683&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84921628683&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-13075-0_30
DO - 10.1007/978-3-319-13075-0_30
M3 - Chapter
AN - SCOPUS:84921628683
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 376
EP - 386
BT - Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings
A2 - Ahn, Hee-Kap
A2 - Shin, Chan-Su
PB - Springer Verlag
ER -