Sie sind hier

# Fixed Parameter Complexity and Approximability of Norm Maximization

Dipl.-Math. Stefan König (TU München)

The problem of maximizing (the p-th power of) a p-norm over a halfspace-presented polytope in R^d is a convex maximization problem which plays a fundamental role in computational convexity. It has been shown in 1986 that this problem is NP-hard for all values p in N, if the dimension d of the ambient space is part of the input. In this paper, we use the theory of parametrized 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, but that for all p in N \ {1} norm maximization is W[1]-hard. We also 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 whose running time depends polynomially on the accuracy. Similarly to the NP-hardness of norm maximization, the W[1]-hardness immediately carries over to various radius computation problems in computational convexity.

(joint work with Christian Knauer and Daniel Werner)

Date
Speaker
Location
Language
14.05.2013 14:15
Stefan König
TEL 512
english