Geometric Optimization Problems Likely Not Contained in APX
Andreas Brieden · 2002
Maximizing geometric functionals such as the classical lp-norms over poly- topes 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 lp-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 n , numbers c ij , 1 ≤ i ≤ j ≤ n, are given and the goal is to maximize 1≤i≤ j≤n c ij xi xj 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 lp-norm-maximum and various lp-radii of centrally symmetric polytopes for 2 ≤ p < ∞.