Fixed-parameter complexity and approximability of norm maximization

DOI10.1007/S00454-015-9667-0MaRDI QIDQ2340407zbMATH OpenOpenAlexFDO

Authors Christian Knauer, Stefan König, Daniel Werner

Publication date 16 April 2015

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.6414

zbMATH Keywords

computational geometryapproximation algorithmscomputational convexityfixed parameter complexityunbounded dimension

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Computational aspects related to convexity (52B55)

Abstract: 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 $pinmathbbN$, 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 $pinmathbbNsetminus1$ 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.

Recommendations

• Computational complexity of norm-maximization
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
• A Variable-Complexity Norm Maximization Problem
• scientific article; zbMATH DE number 1560333

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1182920 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Variable-Complexity Norm Maximization Problem
• Computational Complexity
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• Computational complexity of norm-maximization
• Computational geometry. Algorithms and applications.
• Deterministic and randomized polynomial‐time approximation of radii
• Fixed-parameter tractability and lower bounds for stabbing problems
• Fundamentals of parameterized complexity
• Geometric clustering, fixed-parameter tractability and lower bounds with respect to the dimension
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• Good and Bad Radii of Convex Polygons
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Linear Programming in Linear Time When the Dimension Is Fixed
• Lower bounds based on the exponential time hypothesis
• On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
• On the complexity of \(k\)-SAT
• Parametrized complexity theory.
• The Complexity of Geometric Problems in High Dimension
• The parameterized complexity of some geometric problems in unbounded dimension
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(4)

• A Variable-Complexity Norm Maximization Problem
• The computational complexity of duality
• Computational complexity of norm-maximization
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)

This page was built for publication: Fixed-parameter complexity and approximability of norm maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340407)