Journal: Theoretical Computer Science

Abbreviation

Theor. comp. sci.

Publisher

Elsevier

Journal Volumes

ISSN

0304-3975

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 110
  • Mapping a polygon with holes using a compass
    Item type: Journal Article
    Disser, Yann; Ghosh, Subir Kumar; Mihalák, Matúš; et al. (2014)
    Theoretical Computer Science
  • Two-dimensional drift analysis: Optimizing two functions simultaneously can be hard
    Item type: Journal Article
    Janett, Duri; Lengler, Johannes (2023)
    Theoretical Computer Science
    In this paper we show how to use drift analysis in the case of two random variables X1,X2, when the drift is approximatively given by A⋅(X1,X2)T for a matrix A. The non-trivial case is that X1 and X2 impede each other's progress, and we give a full characterization of this case. As an application, we develop and analyze a minimal example TWOLIN of a dynamic environment that can be hard. The environment consists of two linear functions f1 and f2 with positive weights, and in each generation selection is based on one of them at random. They only differ in the set of positions that have weight 1 and n. We show that the (1+1)-EA with mutation rate χ/n is efficient for small χ on TWOLIN, but does not find the shared optimum in polynomial time for large χ.
  • On the complexity of bribery with distance restrictions
    Item type: Journal Article
    Yang, Yongjie; Shrestha, Yash R.; Guo, Jiong (2019)
    Theoretical Computer Science
  • Exponential slowdown for larger populations: The (μ + 1)-EA on monotone functions
    Item type: Journal Article
    Lengler, Johannes; Zou, Xun (2021)
    Theoretical Computer Science
    Pseudo-Boolean monotone functions are unimodal functions which are trivial to optimize for some hillclimbers, but are challenging for a surprising number of evolutionary algorithms. A general trend is that evolutionary algorithms are efficient if parameters like the mutation rate are set conservatively, but may need exponential time otherwise. In particular, it was known that the (1+1)-EA and the (1+λ)-EA can optimize every monotone function in pseudolinear time if the mutation rate is c/n for some c<1, but that they need exponential time for some monotone functions for c>2.2. The second part of the statement was also known for the (μ+1)-EA. In this paper we show that the first statement does not apply to the (μ+1)-EA. More precisely, we prove that for every constant c>0 there is a constant μ0∈N such that the (μ+1)-EA with mutation rate c/n and population size μ0≤μ≤n needs superpolynomial time to optimize some monotone functions. Thus, increasing the population size by just a constant has devastating effects on the performance. This is in stark contrast to many other benchmark functions on which increasing the population size either increases the performance significantly, or affects performance only mildly. The reason why larger populations are harmful lies in the fact that larger populations may temporarily decrease the selective pressure on parts of the population. This allows unfavorable mutations to accumulate in single individuals and their descendants. If the population moves sufficiently fast through the search space, then such unfavorable descendants can become ancestors of future generations, and the bad mutations are preserved. Remarkably, this effect only occurs if the population renews itself sufficiently fast, which can only happen far away from the optimum. This is counter-intuitive since usually optimization becomes harder as we approach the optimum. Previous work missed the effect because it focused on monotone functions that are only deceptive close to the optimum.
  • On the number of upward planar orientations of maximal planar graphs
    Item type: Journal Article
    Frati, F.; Gudmundsson, J.; Welzl, E. (2014)
    Theoretical Computer Science
  • The string guessing problem as a method to prove lower bounds on the advice complexity
    Item type: Journal Article
    Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; et al. (2014)
    Theoretical Computer Science
  • A simple optimal contention resolution scheme for uniform matroids
    Item type: Journal Article
    Kashaev, Danish; Santiago, Richard (2023)
    Theoretical Computer Science
  • Reoptimization of Steiner trees
    Item type: Journal Article
    Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Královič, Richard; et al. (2009)
    Theoretical Computer Science
  • Symmetry Breaking Depending on the Chromatic Number or the Neighborhood Growth
    Item type: Journal Article
    Schneider, Johannes; Elkin, Michael; Wattenhofer, Roger (2013)
    Theoretical Computer Science
  • Theory and Applications of Models of Computation at the Turing Centenary in China : Preface
    Item type: Other Journal Item
    Mor, Tal; Renner, Renato (2014)
    Theoretical Computer Science
Publications 1 - 10 of 110