Optimal Bound on the Combinatorial Complexity of Approximating Polytopes

DOI10.1137/1.9781611975994.48MaRDI QIDQ5146818zbMATH OpenOpenAlexFDO

Authors Rahul Arya, Sunil Arya, David M. Mount, Guilherme D. Da Fonseca

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.14459

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
• On the combinatorial complexity of approximating polytopes
• On the combinatorial complexity of approximating polytopes
• Optimal volume-sensitive bounds for polytope approximation
• Optimal area-sensitive bounds for polytope approximation

Cited in

(7)

• On the complexity of approximating the maximal inscribed ellipsoid for a polytope
• Oracle-polynomial-time approximation of largest simplices in convex bodies
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
• On the polytope faces of the graph approximation problem
• Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
• Optimal volume-sensitive bounds for polytope approximation

This page was built for publication: Optimal Bound on the Combinatorial Complexity of Approximating Polytopes

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