Dear all,
since many interesting papers in the theory of randomized search heuristics have been written recently, Benjamin and I would like to organize another short round of online talks before the summer break. We are planning talks every Monday at 14.00 CEST (12.00 UTC), starting from May 13 and ending on June 24. We are proud to announce Dirk Sudholt as our first speaker (see detailed information below).
All talks will take place in the following permanent Zoom meeting:
https://dtudk.zoom.us/j/65818691920?pwd=cGY1aWsraXZXUHRtVEpJc3Vicy92dz09Information on all talks will be collected on
https://thrash-seminars.github.io/.
We encourage everyone interested to suggest a talk by sending an e-mail to Benjamin and me. Typically, we allocate 1 hour for each session but ideally, the talk itself would last at most 30 minutes to allow ample time for discussion. The second talk in the series will be on May 27 because of a public holiday in many countries on May 20. Afterwards, we are planning weekly talks.
Looking forward to a series of exciting talks.
Best wishes,
Benjamin and Carsten
------------------------------------------------------------------------------------------------
Details of the first talk on May 13:
Speaker: Dirk Sudholt, University of Passau, Germany
Title:
Evolutionary Computation Meets Graph Drawing: Runtime Analysis for Crossing Minimisation on Layered Graph Drawings
Abstract:
Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on a horizontal line and edges are drawn as $y$-monotone curves. A key ingredient for constructing such drawings is the One-Sided Bipartite Crossing Minimization (OBCM) problem: given two layers of a bipartite graph and a fixed horizontal order of vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We analyse the performance of simple evolutionary algorithms for OBCM and compare different operators for permutations: exchanging two elements, swapping adjacent elements and jumping an element to a new position. We show that the simplest and cheapest mutation operator, swap, shows excellent performance on instances that can be drawn crossing-free, which correspond to a generalised sorting problem. We give a tight runtime bound of $\Theta(n
2)$ via a parallel BubbleSort algorithm and a delay sequence argument. This gives a positive answer to an open problem from Scharnow, Tinnefeld, and Wegener (2004) on whether the best known bound of $O(n
2 \log n)$ for sorting in permutation spaces can be improved to $\Theta(n
2)$, albeit for an even simpler operator.