Filters

Settings

Now showing1 - 2 of 2
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Fixed-parameter complexity and approximability of norm maximization
    (Springer, 2015-02-21)
    Knauer, Christian
    ;
    König, Stefan
    ;
    Werner, Daniel
    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.
    Publicationtype: Journal Article
      63
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Coloring d-embeddable k-uniform hypergraphs
    (Springer, 2014-10-17)
    Heise, Carl Georg
    ;
    Panagiotou, Konstantinos
    ;
    Pikhurko, Oleg
    ;
    Taraz, Anusch
    This paper extends the scenario of the Four Color Theorem in the following way. Let Hd,k be the set of all k-uniform hypergraphs that can be (linearly) embedded into Rd. We investigate lower and upper bounds on the maximum (weak) chromatic number of hypergraphs in Hd,k. For example, we can prove that for (Formula presented.) there are hypergraphs in H2d-3,d on n vertices whose chromatic number is Ω(log n/log log n), whereas the chromatic number for n-vertex hypergraphs in Hd,d is bounded by (Formula presented.).
    Publicationtype: Journal Article
      65