Complexity of approximating the vertex centroid of a polyhedron

DOI10.1016/J.TCS.2011.11.017MaRDI QIDQ764376zbMATH OpenOpenAlexFDO

Authors Hans Raj Tiwary, Khaled Elbassioni

Publication date 13 March 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.11.017

zbMATH Keywords

centroidpolytopeNP-hardcentroid computationcentroid approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects related to convexity (52B55)

Recommendations

• Complexity of approximating the vertex centroid of a polyhedron
• Approximating the centroid is hard
• On the Complexity of Computing the Volume of a Polyhedron
• scientific article; zbMATH DE number 4108152
• Polynomial-time approximation of largest simplices in \(V\)-polytopes.

Cites work

• Approximating the centroid is hard
• Generating all vertices of a polyhedron is hard
• Hard Enumeration Problems in Geometry and Combinatorics
• How good are convex hull algorithms?
• Lectures on Polytopes
• On the Complexity of Computing the Volume of a Polyhedron
• On the hardness of computing intersection, union and Minkowski sum of polytopes
• Random walks and anO*(n5) volume algorithm for convex bodies
• The Complexity of Vertex Enumeration Methods

Cited in

(6)

• Centroids of the core of exact capacities: a comparative study
• Complexity of approximating the vertex centroid of a polyhedron
• Approximating the centroid is hard
• Penalty-based aggregation of multidimensional data
• A center of a polytope: An expository review and a parallel implementation
• Centroids of credal sets: a comparative study

This page was built for publication: Complexity of approximating the vertex centroid of a polyhedron

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764376)