Verlagslink DOI: 10.1007/s00454-015-9667-0
Titel: Fixed-parameter complexity and approximability of norm maximization
Sprache: Englisch
Autor/Autorin: Knauer, Christian 
König, Stefan 
Werner, Daniel 
Schlagwörter: Approximation algorithms; Computational convexity; Computational geometry; Fixed parameter complexity; Unbounded dimension
Erscheinungs­datum: 21-Feb-2015
Verlag: Springer
Quellenangabe: Discrete and Computational Geometry 53 (2): 276-295 (2015-03)
Zusammenfassung (englisch): 
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.
URI: http://hdl.handle.net/11420/10089
ISSN: 1432-0444
Zeitschrift: Discrete & computational geometry 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

41
Letzte Woche
0
Letzten Monat
1
checked on 01.10.2022

SCOPUSTM   
Zitate

2
Letzte Woche
0
Letzten Monat
0
checked on 29.06.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.