Publisher DOI: 10.1007/s00454-015-9667-0
Title: Fixed-parameter complexity and approximability of norm maximization
Language: English
Authors: Knauer, Christian 
König, Stefan 
Werner, Daniel 
Keywords: Approximation algorithms; Computational convexity; Computational geometry; Fixed parameter complexity; Unbounded dimension
Issue Date: 21-Feb-2015
Publisher: Springer
Source: Discrete and Computational Geometry 53 (2): 276-295 (2015-03)
Abstract (english): 
The problem of maximizing the pth power of a p-norm over a halfspace-presented polytope in ℝd is a convex maximization problem which plays a fundamental role in computational convexity. Mangasarian and Shiau showed in 1986 that this problem is ℕℙ-hard for all values p ∈ ℕ if the dimension d of the ambient space is part of the input. In this paper, we use the theory of parameterized 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 (in FPT for short) but that for all p > 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 with a running time depending polynomially on the accuracy. As with the ℕℙ-hardness of norm maximization, the W[1]-hardness immediately carries over to various radius computation tasks in computational convexity.
ISSN: 1432-0444
Journal: Discrete & computational geometry 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 6, 2022


Last Week
Last month
checked on Jun 29, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.