Fixed-parameter complexity and approximability of norm maximization

DOI10.1007/S00454-015-9667-0zbMATH Open1309.68200arXiv1307.6414OpenAlexW2126147154MaRDI QIDQ2340407FDOQ2340407

Stefan König, Christian Knauer, Daniel Werner

Publication date: 16 April 2015

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Computational Complexity
• Parametrized complexity theory.
• On the complexity of \(k\)-SAT
• Linear Programming in Linear Time When the Dimension Is Fixed
• Deterministic and randomized polynomial‐time approximation of radii
• A Variable-Complexity Norm Maximization Problem
• Tight lower bounds for certain parameterized NP-hard problems
• Geometric clustering
• On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
• Fixed-parameter tractability and lower bounds for stabbing problems
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• Computational complexity of norm-maximization
• Good and Bad Radii of Convex Polygons
• The Complexity of Geometric Problems in High Dimension
• The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension

Cited In (1)

• Title not available (Why is that?)

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)