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 -