# Computing the Löwner-John ellipsoid of a polyhedron

The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations available if $C$ is (the convex hull of) a set of points.

Are there fast (i.e non-ellipsoid-method based) approximations to the MVE of a bounded polyhedron presented only in terms of the halfplanes whose intersections define it ? In particular, I'd be interested in methods that run in time polynomial in the dimension and the inverse error $1/\varepsilon$.

-
do we even know how to compute/approximate the radius of the polyhedron in this regime? because without that I don't even see a separation oracle for the ellipsoid algorithm –  Sasho Nikolov Dec 22 '12 at 12:14

## 1 Answer

According to Boyd, it's NP-hard: http://youtu.be/mNzu42FrlHo?t=41m3s

-
Interesting. and he also suggests that the opposite is true for max volume inscribed ellipsoid (easy for the H-rep, but hard for the V-rep). I'm still hoping there are some good approiximations, so I'll hold off on accepting the answer, but I'll revisit in a day or two. –  Suresh Venkat Dec 22 '12 at 22:54