The computational complexity of convex bodies

Details The computational complexity of convex bodies The computational complexity of convex bodies

2006-10-10

arxiv.org/abs/math/0610325v1

Mathematics

Metric Geometry

24 pages

Scientific paper

We 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.

Affiliated with

Also associated with

No associations

Rating

The computational complexity of convex bodies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The computational complexity of convex bodies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computational complexity of convex bodies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-438163