The chair has 5 new papers to present at 2 different conferences.
Mixed Discrete-Continuous Optimization: Even Separable Problems Are Not That Simple: In the field of the analysis of evolutionary computation, the focus is usually on discrete or continuous optimization problems. But since mixed discrete-continuous optimization problems arise frequently in practice, we considered them and showed that even for separable problems, they can present nontrivial challenges for algorithms.
Theoretical Analysis of the (1+1)-EA-ES with Reduced Success Rule for Mixed-Discrete-Continuous Optimization: In this paper, we provided, to the best of our knowledge, the first complete theoretical analysis of a hybrid discrete-continuous algorithm in the mixed optimization context. We proved for the (1+1)-EA-ES with reduced success rule a bound on the expected time to reach an epsilon neighborhood of the optimum.
Both papers were written by Jurek Sander, Priv.-Doz. Dr. Timo Kötzing, Anne Auger and Dimo Brockhoff.
The paper First Hitting Times for Multiple Processes and Targets was written by Priv.-Doz. Dr. Timo Kötzing and Prof. Dr. Jon Rowe and presents one new drift theorems and one new theorem on the fitness level method. Both address the first time that, in a collection of n processes, each has obtained their goal state at least once. In contrast to classical theorems in this area, the theorems incur essentially an additional log factor to find that all processes have achieved their goals, but, in certain settings, also allow for better bounds.
The paper Targets und Combinatorial Landscape Analysis for Dominating Set and Vertex Coloring was written by our current Bachelor students Johanna Gasse, Antonia Heinen, Felix Knöfel and Maxim Stanko together with Priv.-Doz. Dr. Timo Kötzing and studies the landscapes of the well-known Dominating Set and Vertex Coloring problems. We consider certain neighborhoods, such as removing and adding a vertex (for Dominating Set) or recoloring a vertex (for Vertex Coloring). Our results show that graphs from certain graph classes have no local optima (which are not global optima), while graphs from other graph classes have such local optima.
All these 4 papers will be presented at the PPSN 2026 in Trento, Italy from August 29 - September 2.
An Entropy Potential for Type-Composition Games was written by Merlin de la Haye, Marcus Pappik, Dr. Morteza Alimi, Dr. Šimon Schierreich and Jun. Prof. Dr. Alex Skopalik
Potential functions are a powerful tool in theoretical computer science, used to analyze the runtime of algorithms, the expected behavior of random processes, and to prove the existence of equilibrium states in strategic games.
We introduce a novel way of building potential functions with log-multinomials, inspired by entropy.
The paper has a special focus on simplicity in presentation, and we explain how this new potential can be used in a game-theoretic setting to simplify proofs for two recent game-theoretic models and extend previous results to a broader range of models.
In these models, rational agents choose one of a set of different actions and base their utilities on the fraction of other- and same-type agents taking the same action.
The paper will be presented at the Easy Peasy at EC'26 in Rome, Italy on July 6.
