Back to Search
Start Over
An FPTAS for the volume of some [formula omitted]-polytopes — It is hard to compute the volume of the intersection of two cross-polytopes.
- Source :
-
Theoretical Computer Science . Sep2020, Vol. 833, p87-106. 20p. - Publication Year :
- 2020
-
Abstract
- • We present a deterministic approximation algorithm for a #P-hard problem. • Our algorithm is a fully polynomial time approximation scheme (FPTAS). • To this end, the intersection volume of two cross-polytopes is also considered. • We propose an FPTAS also for the intersection volume of cross-polytopes. • We prove that computing the intersection volume is, surprisingly, still #P-hard. 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 (n / log n) n. 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 V -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) [16]. We reduce an approximate volume of a knapsack dual polytope to that of the intersection of two cross-polytopes in a short distance, and give FPTASs for those volume computations. Interestingly, computing the volume of the intersection of two cross-polytopes (i.e., L 1 -balls) is #P-hard, unlike the cases of L ∞ -balls or L 2 -balls. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 833
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 144789106
- Full Text :
- https://doi.org/10.1016/j.tcs.2020.05.029