@inproceedings{48843,
  abstract     = {{We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical graph coloring problem and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. This includes the (1+1) EA and RLS in a setting where the number of colors is bounded and we are minimizing the number of conflicts as well as iterated local search algorithms that use an unbounded color palette and aim to use the smallest colors and - as a consequence - the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i. e. starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. Furthermore, we show how to speed up computations by using problem specific operators concentrating on parts of the graph where changes have occurred.}},
  author       = {{Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-6111-8}},
  keywords     = {{dynamic optimization, evolutionary algorithms, running time analysis, theory}},
  pages        = {{1443–1451}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring}}},
  doi          = {{10.1145/3321707.3321792}},
  year         = {{2019}},
}

@inproceedings{48840,
  abstract     = {{Research has shown that for many single-objective graph problems where optimum solutions are composed of low weight sub-graphs, such as the minimum spanning tree problem (MST), mutation operators favoring low weight edges show superior performance. Intuitively, similar observations should hold for multi-criteria variants of such problems. In this work, we focus on the multi-criteria MST problem. A thorough experimental study is conducted where we estimate the probability of edges being part of non-dominated spanning trees as a function of the edges’ non-domination level or domination count, respectively. Building on gained insights, we propose several biased one-edge-exchange mutation operators that differ in the used edge-selection probability distribution (biased towards edges of low rank). Our empirical analysis shows that among different graph types (dense and sparse) and edge weight types (both uniformly random and combinations of Euclidean and uniformly random) biased edge-selection strategies perform superior in contrast to the baseline uniform edge-selection. Our findings are in particular strong for dense graphs.}},
  author       = {{Bossek, Jakob and Grimme, Christian and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-6111-8}},
  keywords     = {{biased mutation, combinatorial optimization, minimum spanning tree, multi-objective optimization}},
  pages        = {{516–523}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{On the Benefits of Biased Edge-Exchange Mutation for the Multi-Criteria Spanning Tree Problem}}},
  doi          = {{10.1145/3321707.3321818}},
  year         = {{2019}},
}