@misc{BiloFriedrichLenzneretal.2019,
  author    = {Bilo, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna},
  title     = {Geometric Network Creation Games},
  series = {SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures},
  journal   = {SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures},
  publisher = {Association for Computing Machinery},
  address   = {New York},
  isbn      = {978-1-4503-6184-2},
  doi       = {10.1145/3323165.3323199},
  pages     = {323 -- 332},
  year      = {2019},
  abstract  = {Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.},
  language  = {en}
}
@misc{KoetzingLagodzinskiLengleretal.2018,
  author    = {K{\"o}tzing, Timo and Lagodzinski, Gregor J. A. and Lengler, Johannes and Melnichenko, Anna},
  title     = {Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming},
  series = {Parallel Problem Solving from Nature - PPSN XV},
  volume    = {11102},
  journal   = {Parallel Problem Solving from Nature - PPSN XV},
  publisher = {Springer},
  address   = {Cham},
  isbn      = {978-3-319-99259-4},
  issn      = {0302-9743},
  doi       = {10.1007/978-3-319-99259-4_4},
  pages     = {42 -- 54},
  year      = {2018},
  abstract  = {For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); the resulting algorithm is denoted Concatenation Crossover GP. For this purpose three variants of the wellstudied Majority test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control.},
  language  = {en}
}