1. Goffin´s algorithm for zonotopes
- Creator:
- Černý, Michal
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- Löwner-John ellipse, zonotope, Goffin´s algorithm, and ellipsoid method
- Language:
- English
- Description:
- The Löwner-John ellipse of a full-dimensional bounded convex set is a circumscribed ellipse with the property that if we shrink it by the factor n (where n is dimension), we obtain an inscribed ellipse. Goffin's algorithm constructs, in polynomial time, a tight approximation of the Löwner-John ellipse of a polyhedron given by facet description. In this text we adapt the algorithm for zonotopes given by generator descriptions. We show that the adapted version works in time polynomial in the size of the generator description (which may be superpolynomially shorter than the facet description).
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public