Complexity of approximating the vertex centroid of a polyhedron

DOI10.1016/j.tcs.2011.11.017zbMath1232.68072OpenAlexW2081502538MaRDI QIDQ764376

Hans Raj Tiwary, Khaled M. 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

polytopeNP-hardcentroidcentroid computationcentroid approximation

Mathematics Subject Classification ID

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

Related Items

Centroids of credal sets: a comparative study ⋮ Centroids of the core of exact capacities: a comparative study ⋮ Penalty-based aggregation of multidimensional data

Cites Work

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