# Fixed Parameter Complexity and Approximability of Norm Maximization

arXiv: https://arxiv.org/abs/1307.6414 · HTML: https://mlsanity.com/paper/1307.6414/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2013.

## Built on by (most cited first, 2 of 2)

- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Parameterized Complexity of Lp-Lipschitz Constants for Input Convex Neural Networks and Lp-Norm Maximization over Zonotopes](https://mlsanity.com/paper/2608.24865/) (2026)

## Abstract (arXiv)

The problem of maximizing the p-th 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 shown in 1986 that this problem is NP-hard for all values p ∈ mathbbN, 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 ∈ mathbbN setminus 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, the running time of which depends polynomially on the accuracy. As with the NP-hardness of norm maximization, the W[1]-hardness immediately carries over to various radius computation tasks in Computational Convexity.