Charl Ras: The multi-source multi-sink directed Steiner tree problem in the plane
21 November 2023 - 21 November 2023
East Campus USI-SUPSI Room B1.14
The Euclidean Steiner tree problem requires a shortest network interconnecting a given set of points in the plane. Additional vertices may be introduced and are called Steiner points. This is a well-studied, but NP-hard problem. Nevertheless, the current flagship algorithm can exactly solve instances on many thousands of input points. There are many variations to this classical problem. In this presentation we will look at a multi-source multi-sink directed version. For two given sets of points A (the sources) and B (the sinks), the task is to find a minimum length network such that there exists a directed path between every source and every sink. We will share some known structural results on optimal solutions and discuss the current state of algorithmic approaches for finding exact solutions.

The Speaker

Charl Ras is an Associate Professor in Operations Research at the School of Mathematics and Statistics at the University of Melbourne. Charl’s interests lie in geometric network design (including Steiner trees), algorithmics, and combinatorial optimisation.