4 papers
From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization
Lukas Behrendt, Katrin Casel, Tobias Friedrich +3
We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the…
Bounding Bloat in Genetic Programming
Benjamin Doerr, Timo Kötzing, J. A. Gregor Lagodzinski +1
While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on vari…
Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming
Timo Kötzing, J. A. Gregor Lagodzinski, Johannes Lengler +1
For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yieldi…
Counting Homomorphisms to Trees Modulo a Prime
Andreas Göbel, J. A. Gregor Lagodzinski, Karen Seidel
Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular, independent sets a…