Friday, 10:30 - 10:55 h, Room: H 0112


Stefan K├Ânig
Norm maximization is W[1]-hard

Coauthors: Christian Knauer, Daniel Werner


The problem of maximizing the pth power of a p-norm over a halfspace presented polytope in Rd is a convex maximization problem which plays a fundamental role in computational convexity. It has been known since 1986 that this problem is NP-hard for all values p ∈ N, if the dimension d of the ambient space is considered as part of the input.
In recent years, the theory of parametrized complexity has become a helpful tool in analysing how the hardness of problems depends on specific parameters of the input.
In this talk, we will briefly discuss the prerequisites from parametrized complexity and then investigate the complexity of norm maximization with the natural choice of d as parameter.
More precisely, we show that, for p=1, the problem is fixed parameter tractable (i.e., it can be considered as computationally feasible if only the dimension d is small) but that, for all p ∈ N \ {1}, norm maximization is W[1]-hard. The presented reduction also yields that, under standard complexity theoretic assumptions, there is no algorithm with running time no(d) that answers the problem correctly.


Talk 1 of the contributed session Fri.1.H 0112
"Complexity issues in optimization" [...]
Cluster 16
"Nonlinear programming" [...]


  loans online . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.