The computational complexity of convex bodies

Simple item page
dc.creatorBarvinok, Alexander
dc.creatorVeomett, Ellen
dc.date2006-10-10
dc.date.accessioned2026-07-07T07:28:54Z
dc.date.available2026-07-07T07:28:54Z
dc.descriptionWe discuss how well a given convex body B in a real d-dimensional vector space V can be approximated by a set X for which the membership question: ``given an x in V, does x belong to X?'' can be answered efficiently (in time polynomial in d). We discuss approximations of a convex body by an ellipsoid, by an algebraic hypersurface, by a projection of a polytope with a controlled number of facets, and by a section of the cone of positive semidefinite quadratic forms. We illustrate some of the results on the Traveling Salesman Polytope, an example of a complicated convex body studied in combinatorial optimization.
dc.description24 pages
dc.identifierhttps://arxiv.org/abs/math/0610325
dc.identifierhttp://arxiv.org/abs/math/0610325
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/117904
dc.subjectMetric Geometry
dc.subjectCombinatorics
dc.subject52A20, 52A27, 52A21, 52B55, 68W25, 68Q25
dc.titleThe computational complexity of convex bodies
dc.typetext

Files

Collections

arXiv