TY - GEN

T1 - Complexity of approximating the vertex centroid of a polyhedron

AU - Elbassioni, Khaled

AU - Tiwary, Hans Raj

N1 - Funding Information:
✩During part of this work the second author was supported by Graduiertenkolleg fellowship for Ph.D. studies provided by Deutsche Forschungsgemeinschaft.∗ Correspondingauthor.Tel.:+496819325107. E-mail addresses: [email protected] (K. Elbassioni), [email protected] (H.R. Tiwary).

PY - 2009

Y1 - 2009

N2 - Let be an -polytope in ℝ d with vertex set V. The vertex centroid is defined as the average of the vertices in V. We first prove that computing the vertex centroid of an -polytope, or even just checking whether it lies in a given halfspace, are #P-hard. We also consider the problem of approximating the vertex centroid by finding a point within an ε distance from it and prove this problem to be #P-easy by showing that given an oracle for counting the number of vertices of an -polytope, one can approximate the vertex centroid in polynomial time. We also show that any algorithm approximating the vertex centroid to any "sufficiently" non-trivial (for example constant) distance, can be used to construct a fully polynomial-time approximation scheme for approximating the centroid and also an output-sensitive polynomial algorithm for the Vertex Enumeration problem. Finally, we show that for unbounded polyhedra the vertex centroid can not be approximated to a distance of for any fixed constant δ>0.

AB - Let be an -polytope in ℝ d with vertex set V. The vertex centroid is defined as the average of the vertices in V. We first prove that computing the vertex centroid of an -polytope, or even just checking whether it lies in a given halfspace, are #P-hard. We also consider the problem of approximating the vertex centroid by finding a point within an ε distance from it and prove this problem to be #P-easy by showing that given an oracle for counting the number of vertices of an -polytope, one can approximate the vertex centroid in polynomial time. We also show that any algorithm approximating the vertex centroid to any "sufficiently" non-trivial (for example constant) distance, can be used to construct a fully polynomial-time approximation scheme for approximating the centroid and also an output-sensitive polynomial algorithm for the Vertex Enumeration problem. Finally, we show that for unbounded polyhedra the vertex centroid can not be approximated to a distance of for any fixed constant δ>0.

UR - http://www.scopus.com/inward/record.url?scp=75649109701&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10631-6_43

DO - 10.1007/978-3-642-10631-6_43

M3 - Conference contribution

AN - SCOPUS:75649109701

SN - 3642106307

SN - 9783642106309

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 413

EP - 422

BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings

T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009

Y2 - 16 December 2009 through 18 December 2009

ER -