An FPTAS for the Volume of a V{\cal V}-polytope ---It is Hard to Compute The Volume of The Intersection of Two Cross-polytopes

preprint2016arXivOpen access

Abstract

Given an nn-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(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 V{\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., L1L_1-balls) is #P-hard, unlike the cases of L∞L_{\infty}-balls or L2L_2-balls.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.