| Title:
|
Goffin's algorithm for zonotopes (English) |
| Author:
|
Černý, Michal |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
5 |
| Year:
|
2012 |
| Pages:
|
890-906 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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). (English) |
| Keyword:
|
Löwner–John ellipse |
| Keyword:
|
zonotope |
| Keyword:
|
Goffin's algorithm |
| Keyword:
|
ellipsoid method |
| MSC:
|
52B12 |
| MSC:
|
52B55 |
| MSC:
|
68U05 |
| MSC:
|
90C57 |
| idMR:
|
MR3086858 |
| . |
| Date available:
|
2012-12-17T13:30:19Z |
| Last updated:
|
2013-09-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143088 |
| . |
| Reference:
|
[1] Avis, D., Fukuda, K.: Reverse search for enumeration..Disc. Appl. Math. 65 (1996), 21-46. Zbl 0854.68070, MR 1380066, 10.1016/0166-218X(95)00026-N |
| Reference:
|
[2] Bland, R. G., Goldfarb, D., Todd, M. J.: The ellipsoid method: a survey..Oper. Res. 29 (1981), 1039-1091. Zbl 0474.90056, MR 0641676, 10.1287/opre.29.6.1039 |
| Reference:
|
[3] Buck, R. C.: Partion of space..Amer. Math. Monthly 50 (1943), 541-544. MR 0009119, 10.2307/2303424 |
| Reference:
|
[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. |
| Reference:
|
[5] Ferrez, J.-A., Fukuda, K., Liebling, T.: Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm..Europ. J. Oper. Res. 166 (2005), 35-50. Zbl 1066.90101, MR 2128976, 10.1016/j.ejor.2003.04.011 |
| Reference:
|
[6] Goffin, J.-L.: Variable metric relaxation methods. Part II: The ellipsoid method..Math. Programming 30 (1984), 147-162. MR 0758001, 10.1007/BF02591882 |
| Reference:
|
[7] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization..Springer Verlag, Berlin 1993. Zbl 0837.05001, MR 1261419 |
| Reference:
|
[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. Zbl 1092.68697, MR 1974996 |
| Reference:
|
[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. Zbl 0034.10503, MR 0030135 |
| Reference:
|
[10] Schön, S., Kutterer, H.: Using zonotopes for overestimation-free interval least-squares - some geodetic applications..Reliable Computing 11 (2005), 137-155. Zbl 1073.65034, MR 2147804, 10.1007/s11155-005-3034-4 |
| Reference:
|
[11] Schrijver, A.: Theory of Linear and Integer Programming..Wiley, New York 2000. Zbl 0970.90052, MR 0874114 |
| Reference:
|
[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. |
| Reference:
|
[13] Zaslavsky, T.: Facing up to arrangements: face-count formulas for partitions of space by hyperplanes..Mem. Amer. Math. Soc. 154 (1975), 102 pp. Zbl 0296.50010, MR 0357135 |
| Reference:
|
[14] Ziegler, G.: Lectures on Polytopes..Springer Verlag, Berlin 2004. Zbl 0823.52002, MR 1311028 |
| . |
