Now showing items 1-4 of 4

    • An empirical assessment of local and population based search methods with different degrees of pseudorandomness 

      Arbeitspapier
      Maucher, Markus; Schöning, Uwe; Kestler, Hans A.
      When designing and analyzing randomized algorithms, one usually assumes that a sequence of uniformly distributed, independent random variables is available as a source of randomness. Implementing these algorithms, however, ...
    • Constrained ordering 

      Arbeitspapier
      Guttmann, Walter; Maucher, Markus
      We investigate the problem of finding a total order of a finite set that satisfies various local ordering constraints. Depending on the admitted constraints, we provide an efficient algorithm or prove NP-completeness. To ...
    • On the different notions of pseudorandomness 

      Arbeitspapier
      Maucher, Markus; Schöning, Uwe; Kestler, Hans A.
      This article explains the various notions of pseudorandomness, like Martin-L öf randomness, Kolmogorov complexity, Shannon entropy and quasi-randomness. We describe interconnections between these notions and describe how ...
    • On the influence of non-perfect randomness on probabilistic algorithms 

      Dissertation
      Maucher, Markus
      In modern computer science, many problems are solved with the help of probabilistic algorithms. This thesis concentrates on the analysis of algorithms with respect to the employment of random sources that do not provide ...