@article{FriedrichKatzmannKrohmer2018,
  author    = {Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton},
  title     = {Unbounded Discrepancy of Deterministic Random Walks on Grids},
  series = {SIAM journal on discrete mathematics},
  volume    = {32},
  journal   = {SIAM journal on discrete mathematics},
  number    = {4},
  publisher = {Society for Industrial and Applied Mathematics},
  address   = {Philadelphia},
  issn      = {0895-4801},
  doi       = {10.1137/17M1131088},
  pages     = {2441 -- 2452},
  year      = {2018},
  abstract  = {Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs called the rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave in a remarkably similar way: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer [Combin. Probab. Comput., 15 (2006), pp. 815-822] showed that on Z(d), the single vertex discrepancy is only a constant c(d). Other authors also determined the precise value of c(d) for d = 1, 2. All of these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph Z(d). We show that this assumption is crucial by proving that, otherwise, the single vertex discrepancy can become arbitrarily large. For all dimensions d >= 1 and arbitrary discrepancies l >= 0, we construct configurations that reach a discrepancy of at least l.},
  language  = {en}
}
@article{ShiSchirneckFriedrichetal.2018,
  author    = {Shi, Feng and Schirneck, Friedrich Martin and Friedrich, Tobias and K{\"o}tzing, Timo and Neumann, Frank},
  title     = {Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints},
  series = {Algorithmica : an international journal in computer science},
  volume    = {82},
  journal   = {Algorithmica : an international journal in computer science},
  number    = {10},
  publisher = {Springer},
  address   = {New York},
  issn      = {0178-4617},
  doi       = {10.1007/s00453-020-00739-x},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-605295},
  pages     = {3117 -- 3123},
  year      = {2018},
  abstract  = {Rigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical (1+1) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the (1+(λ,λ))GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small.},
  language  = {en}
}