Fixed-parameter complexity and approximability of norm maximization
DOI10.1007/s00454-015-9667-0zbMath1309.68200arXiv1307.6414OpenAlexW2126147154MaRDI QIDQ2340407
Stefan König, Christian Knauer, 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
fixed parameter complexitycomputational geometryapproximation algorithmscomputational convexityunbounded dimension
Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and lower bounds for stabbing problems
- Fundamentals of parameterized complexity
- Computational complexity of norm-maximization
- Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
- Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
- Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
- Parametrized complexity theory.
- Tight lower bounds for certain parameterized NP-hard problems
- Geometric clustering
- Good and Bad Radii of Convex Polygons
- On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
- The Complexity of Geometric Problems in High Dimension
- The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension
- A Variable-Complexity Norm Maximization Problem
- Linear Programming in Linear Time When the Dimension Is Fixed
- Deterministic and randomized polynomial‐time approximation of radii
- Computational Complexity
- On the complexity of \(k\)-SAT
This page was built for publication: Fixed-parameter complexity and approximability of norm maximization
