Efficient algorithms for approximating maximum inscribed sphere in high dimensional polytopes
MetadataShow full item record
Computing maximum inscribed sphere (MaxIS) in high dimensional polytope is a fundamental problem in theorectical computer science, combinatorial optimization, and operation research, and is closely related to the maximum inscribed ellipsoid (MaxIE) problem which is the core problem of interior-point methods for linear programming (LP). One commonly used approach for solving the MaxIS problem is to reduce it to a linear programming (LP) problem with one more dimension and then use existing LP algorithms to solve it. Thus optimally solving the MaxIS problem could be rather costly (i.e., has the same complexity as an LP problem and takes O ( n 3.5 L ) time using the best-known interior-point algorithm, where L is the size of the LP problem). Due to their importance, both problems have been extensively studied in the past. In this dissertation, we present efficient algorithms for computing a (1 - [straight epsilon])-approximation of the MaxIS. Given a bounded polytope P defined by nd -dimensional halfspaces, an interior point O of P, and a constant [straight epsilon]>0, compute an inscribed sphere B of P with radius no smaller than (1 - [straight epsilon]) R opt , where R opt is the radius of the maximum inscribed sphere of P. For polytopes with constant aspect ratio polytopes (also called fat polytopes), we provide an efficient algorithm with complexity O ( nd /[straight epsilon] 3 ). For other polytopes, our algorithm takes O ((( n + 1/[straight epsilon]) nd /[straight epsilon] 2 ) log α) time, where α is the aspect ratio of the polytope. The dependence of our algorithms on the aspect ratio in the time complexities is only logarithmic. To our best knowledge, our algorithms are the first approximation solutions with linear complexity in d and quadratic in n, which is significantly faster than the traditional way of solving the MaxIS problem. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd in 1993 in which a geometric transform is sought to reduce an MaxIE to an MinEE (i.e., Maximum Enclosing Ellipsoid). Our results give an efficient geometric transformation to reduce MaxIS to MinES (Minimum Enclosing Sphere).