TY - GEN
T1 - An FPTAS for the Volume of Some v-polytopes—It is Hard to Compute the Volume of the Intersection of Two Cross-Polytopes
AU - Ando, Ei
AU - Kijima, Shuji
N1 - Funding Information:
Acknowledgments. This work is partly supported by Grant-in-Aid for Scientific Research on Innovative Areas MEXT Japan “Exploring the Limits of Computation (ELC)” (No. 24106008, 24106005) and by JST PRESTO Grant Number JPMJPR16E4, Japan.
Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
N2 - Given an n-dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio. There is a substantial progress on randomized approximation such as Markov chain Monte Carlo for a high-dimensional volume, and for many #P-hard problems, while only a few #P-hard problems are known to yield deterministic approximation. Motivated by the problem of deterministically approximating the volume of a -polytope, that is a polytope with a small number of vertices and (possibly) exponentially many facets, this paper investigates the problem of computing the volume of a “knapsack dual polytope,” which is known to be #P-hard due to Khachiyan (1989). We reduce an approximate volume of a knapsack dual polytope to that of the intersection of two cross-polytopes, and give FPTASs for those volume computations. Interestingly, computing the volume of the intersection of two cross-polytopes (i.e.,-balls) is #P-hard, unlike the cases of-balls or -balls.
AB - Given an n-dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio. There is a substantial progress on randomized approximation such as Markov chain Monte Carlo for a high-dimensional volume, and for many #P-hard problems, while only a few #P-hard problems are known to yield deterministic approximation. Motivated by the problem of deterministically approximating the volume of a -polytope, that is a polytope with a small number of vertices and (possibly) exponentially many facets, this paper investigates the problem of computing the volume of a “knapsack dual polytope,” which is known to be #P-hard due to Khachiyan (1989). We reduce an approximate volume of a knapsack dual polytope to that of the intersection of two cross-polytopes, and give FPTASs for those volume computations. Interestingly, computing the volume of the intersection of two cross-polytopes (i.e.,-balls) is #P-hard, unlike the cases of-balls or -balls.
UR - http://www.scopus.com/inward/record.url?scp=85028455995&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028455995&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-62389-4_2
DO - 10.1007/978-3-319-62389-4_2
M3 - Conference contribution
AN - SCOPUS:85028455995
SN - 9783319623887
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 13
EP - 24
BT - Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings
A2 - Cao, Yixin
A2 - Chen, Jianer
PB - Springer Verlag
T2 - 23rd International Conference on Computing and Combinatorics, COCOON 2017
Y2 - 3 August 2017 through 5 August 2017
ER -