Options
Fixed-parameter complexity and approximability of norm maximization
Publikationstyp
Journal Article
Date Issued
2015-02-21
Sprache
English
Author(s)
Institut
Volume
53
Issue
2
Start Page
276
End Page
295
Citation
Discrete and Computational Geometry 53 (2): 276-295 (2015-03)
Publisher DOI
Scopus ID
Publisher
Springer
The problem of maximizing the pth power of a p-norm over a halfspace-presented polytope in ℝd is a convex maximization problem which plays a fundamental role in computational convexity. Mangasarian and Shiau showed in 1986 that this problem is ℕℙ-hard for all values p ∈ ℕ if the dimension d of the ambient space is part of the input. In this paper, we use the theory of parameterized complexity to analyze how heavily the hardness of norm maximization relies on the parameter d. More precisely, we show that for p = 1 the problem is fixed-parameter tractable (in FPT for short) but that for all p > 1 norm maximization is W[1]-hard. Concerning approximation algorithms for norm maximization, we show that, for fixed accuracy, there is a straightforward approximation algorithm for norm maximization in FPT running time, but there is no FPT-approximation algorithm with a running time depending polynomially on the accuracy. As with the ℕℙ-hardness of norm maximization, the W[1]-hardness immediately carries over to various radius computation tasks in computational convexity.
Subjects
Approximation algorithms
Computational convexity
Computational geometry
Fixed parameter complexity
Unbounded dimension
DDC Class
510: Mathematik