Paper Info
Title
Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces
Abstract
This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of ann-dimensional convex polytope in the space ∝ n equipped with an ℓ p norm or a polytopal norm. The polytopeP is assumed to be presented as the convex hull of finitely many points with rational coordinates (V-presented) or as the intersection of finitely many closed halfspaces defined by linear inequalities with rational coefficients (ℋ-presented). The innerj-radius ofP is the radius of a largestj-ball contained inP; it isP's inradius whenj = n and half ofP's diameter whenj = 1. The outerj-radius measures how wellP can be approximated, in a minimax sense, by an (n — j)-flat; it isP's circumradius whenj = n and half ofP's width whenj = 1. The binary (Turing machine) model of computation is employed. The primary concern is not with finding optimal algorithms, but with establishing polynomial-time computability or NP-hardness. Special attention is paid to the case in whichP is centrally symmetric. When the dimensionn is permitted to vary, the situation is roughly as follows: (a) for general ℋ-presented polytopes in ℓ p spaces with 1<p<∞, all outer radius computations are NP-hard; (b) in the remaining cases (including symmetric ℋ-presented polytopes), some radius computations can be accomplished in polynomial time and others are NP-hard. These results are obtained by using a variety of tools from the geometry of convex bodies, from linear and nonlinear programming, and from the theory of computational complexity. Applications of the results to various problems in mathematical programming, computer science and other fields are included.
Year
DOI
Venue
1993
10.1007/BF01581243
Universität Trier, Mathematik/Informatik, Forschungsbericht
Keywords
DocType
Volume
finite-dimensional normed space,outer j-radii,computational complexity,diameter,linear programming,computational geometry,turing machine,linear program,polytope,circumsphere,sensitivity analysis,nonlinear programming,robotics,quadratic programming,convex body,lp space,lp norm,ellipsoid method,convex hull,polarity,width,convex polytope,mathematical programming,polynomial time,model of computation,normed space,quadratic program,radius
Journal
59
Issue
ISSN
Citations 
2
1436-4646
33
PageRank 
References 
Authors
2.42
5
2
Name
Order
Citations
PageRank
Peter Gritzmann141246.93
Victor Klee216917.23