Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/3876| Title: | An Algorithm for Computing the Symmetry Point of a Polytope |
| Keywords: | symmetry geometry of convex sets interior-point methods |
| Issue Date: | 9-Oct-2013 |
| Description: | Given a closed convex set C and a point x in C, let sym(x,C) denote the symmetry value of x in C, which essentially measures how symmetric C is about the point x. Denote by sym(C) the largest value of sym(x,C) among all x in C, and let x* denote the most symmetric point in C. These symmetry measures are all invariant under linear transformation, change in inner product, etc., and so are of interest in the study of the geometry of convex sets and arise naturally in the evaluation of the complexity of interior-point methods in particular. Herein we show that when C is given by the intersection of halfspaces, i.e., C={x | Ax <= b}, then x* as well as the symmetry value of C can be computed by using linear programming. Furthermore, given an approximate analytic center of C, there is a strongly polynomial-time algorithm for approximating sym(C) to any given relative tolerance. Singapore-MIT Alliance (SMA) |
| URI: | http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
| Other Identifiers: | http://hdl.handle.net/1721.1/3876 |
| Appears in Collections: | MIT Items |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.