Complexity of approximating the vertex centroid of a polyhedron

Khaled Elbassioni, Hans Raj Tiwary

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageBritish English
Pages (from-to)56-61
Number of pages6
JournalTheoretical Computer Science
Volume421
DOIs
StatePublished - 2 Mar 2012

Fingerprint

Dive into the research topics of 'Complexity of approximating the vertex centroid of a polyhedron'. Together they form a unique fingerprint.

Cite this