Complexity of approximating the vertex centroid of a polyhedron
DOI10.1016/J.TCS.2011.11.017zbMATH Open1232.68072OpenAlexW2081502538MaRDI QIDQ764376FDOQ764376
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
Recommendations
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)
Cites Work
- Lectures on Polytopes
- Random walks and anO*(n5) volume algorithm for convex bodies
- Generating all vertices of a polyhedron is hard
- On the hardness of computing intersection, union and Minkowski sum of polytopes
- On the Complexity of Computing the Volume of a Polyhedron
- Hard Enumeration Problems in Geometry and Combinatorics
- How good are convex hull algorithms?
- Approximating the centroid is hard
- The Complexity of Vertex Enumeration Methods
Cited In (6)
- Approximating the centroid is hard
- A center of a polytope: An expository review and a parallel implementation
- Centroids of credal sets: a comparative study
- Centroids of the core of exact capacities: a comparative study
- Complexity of approximating the vertex centroid of a polyhedron
- Penalty-based aggregation of multidimensional data
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)
