2016/07/21 by Ei Ando, Ando, Ei, Shuji Kijima +1
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.1607.06173
openalex publication_date 2016/07/21 · openalex created_date 2016/08/23 · openalex updated_date 2026/07/28
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 some deterministic approximation algorithms are recently developed only for a few #P-hard problems. Motivated by a deterministic approximation of the volume of a \cal V-polytope, that is a polytope with few vertices and (possibly) exponentially many facets, this paper investigates 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, the volume of the intersection of two cross-polytopes (i.e., L1-balls) is #P-hard, unlike the cases of L∞-balls or L2-balls.