Goffin's algorithm for zonotopes

Michal Černý

Kybernetika (2012)

  • Volume: 48, Issue: 5, page 890-906
  • ISSN: 0023-5954

Abstract

top
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).

How to cite

top

Černý, Michal. "Goffin's algorithm for zonotopes." Kybernetika 48.5 (2012): 890-906. <http://eudml.org/doc/251418>.

@article{Černý2012,
abstract = {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).},
author = {Černý, Michal},
journal = {Kybernetika},
keywords = {Löwner–John ellipse; zonotope; Goffin's algorithm; ellipsoid method; Löwner-John ellipse; zonotope; Goffin's algorithm; ellipsoid method},
language = {eng},
number = {5},
pages = {890-906},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Goffin's algorithm for zonotopes},
url = {http://eudml.org/doc/251418},
volume = {48},
year = {2012},
}

TY - JOUR
AU - Černý, Michal
TI - Goffin's algorithm for zonotopes
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 5
SP - 890
EP - 906
AB - 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).
LA - eng
KW - Löwner–John ellipse; zonotope; Goffin's algorithm; ellipsoid method; Löwner-John ellipse; zonotope; Goffin's algorithm; ellipsoid method
UR - http://eudml.org/doc/251418
ER -

References

top
  1. Avis, D., Fukuda, K., 10.1016/0166-218X(95)00026-N, Disc. Appl. Math. 65 (1996), 21-46. Zbl0854.68070MR1380066DOI10.1016/0166-218X(95)00026-N
  2. Bland, R. G., Goldfarb, D., Todd, M. J., 10.1287/opre.29.6.1039, Oper. Res. 29 (1981), 1039-1091. Zbl0474.90056MR0641676DOI10.1287/opre.29.6.1039
  3. Buck, R. C., 10.2307/2303424, Amer. Math. Monthly 50 (1943), 541-544. MR0009119DOI10.2307/2303424
  4. Černý, M., Antoch, J., Hladík, M., On the Possibilistic Approach to Linear Regression Models Involving Uncertain, Indeterminate or Interval Data., Technical Report, Department of Econometrics, University of Economics, Prague 2011. http://nb.vse.cz/ cernym/plr.pdf. 
  5. Ferrez, J.-A., Fukuda, K., Liebling, T., 10.1016/j.ejor.2003.04.011, Europ. J. Oper. Res. 166 (2005), 35-50. Zbl1066.90101MR2128976DOI10.1016/j.ejor.2003.04.011
  6. Goffin, J.-L., 10.1007/BF02591882, Math. Programming 30 (1984), 147-162. MR0758001DOI10.1007/BF02591882
  7. Grötschel, M., Lovász, L., Schrijver, A., Geometric Algorithms and Combinatorial Optimization., Springer Verlag, Berlin 1993. Zbl0837.05001MR1261419
  8. Guibas, L. J., Nguyen, A., Zhang, L., Zonotopes as bounding volumes., In: Proc. Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Pennsylvania 2003, pp. 803-812. Zbl1092.68697MR1974996
  9. John, F., Extremum problems with inequalities as subsidiary conditions., In: Fritz John, Collected Papers (J. Moser, ed.), Volume 2. Birkhäuser, Boston 1985, pp. 543-560. Zbl0034.10503MR0030135
  10. Schön, S., Kutterer, H., 10.1007/s11155-005-3034-4, Reliable Computing 11 (2005), 137-155. Zbl1073.65034MR2147804DOI10.1007/s11155-005-3034-4
  11. Schrijver, A., Theory of Linear and Integer Programming., Wiley, New York 2000. Zbl0970.90052MR0874114
  12. Yudin, D. B., Nemirovski, A. S., Informational complexity and efficient methods for the solution of convex extremal problems., Matekon 13 (3) (1977), 25-45. 
  13. Zaslavsky, T., Facing up to arrangements: face-count formulas for partitions of space by hyperplanes., Mem. Amer. Math. Soc. 154 (1975), 102 pp. Zbl0296.50010MR0357135
  14. Ziegler, G., Lectures on Polytopes., Springer Verlag, Berlin 2004. Zbl0823.52002MR1311028

NotesEmbed ?

top

You must be logged in to post comments.