Geometric Optimization Problems Likely Not Contained in $$\mathbb{A}\mathbb{P}\mathbb{X}$$

   Abstract. Maximizing geometric functionals such as the classical l _p -norms over polytopes plays an important role in many applications, hence it is desirable to know how efficiently the solutions can be computed or at least approximated. While the maximum of the l _∞ -norm over polytopes can be computed in polynomial time, for 2≤ p < ∞ the l _p -norm-maxima cannot be computed in polynomial time within a factor of 1.090 , unless P=NP. This result holds even if the polytopes are centrally symmetric parallelotopes. Quadratic Programming is a problem closely related to norm-maximization, in that in addition to a polytope P ⊂ R ⁿ , numbers c _ij , 1≤ i≤ j≤ n , are given and the goal is to maximize Σ _{1≤ i≤ j≤ n} c _ij x _i x _j over P . It is known that Quadratic Programming does not admit polynomial-time approximation within a constant factor, unless P=NP. Using the observation that the latter result remains true even if the existence of an integral optimal point is guaranteed, in this paper it is proved that analogous inapproximability results hold for computing the l _p -norm-maximum and various l _p -radii of centrally symmetric polytopes for 2≤ p < ∞.