TY - JOUR

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: elbassio@mpi-inf.mpg.de (K. Elbassioni), hans.raj.tiwary@ulb.ac.be (H.R. Tiwary).

PY - 2012/3/2

Y1 - 2012/3/2

N2 - Let P be an H-polytope in R 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 anH-polytope, or even just checking whether it lies in a given halfspace, is 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 in the sense that it can be solved efficiently using an oracle for some P-complete problem. In particular, we show that given an oracle for counting the number of vertices of an H-polytope, one can approximate the vertex centroid in polynomial time. Counting the number of vertices of a polytope defined as the intersection of halfspaces is known to be P-complete. 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 cannot be approximated to a distance of d1 2-δ for any fixed constant δ>0 unless P=NP.

AB - Let P be an H-polytope in R 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 anH-polytope, or even just checking whether it lies in a given halfspace, is 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 in the sense that it can be solved efficiently using an oracle for some P-complete problem. In particular, we show that given an oracle for counting the number of vertices of an H-polytope, one can approximate the vertex centroid in polynomial time. Counting the number of vertices of a polytope defined as the intersection of halfspaces is known to be P-complete. 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 cannot be approximated to a distance of d1 2-δ for any fixed constant δ>0 unless P=NP.

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

U2 - 10.1016/j.tcs.2011.11.017

DO - 10.1016/j.tcs.2011.11.017

M3 - Article

AN - SCOPUS:84856590283

SN - 0304-3975

VL - 421

SP - 56

EP - 61

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -