A new information theory perspective on network design in phylogenetics and beyond


Recent advances on the combinatorics of the Balanced Minimum Evolution Problem (BMEP) have shown that statistically consistent estimation models in phylogenetics are closely related to a class of cross-entropy minimization problems derived from notions of information theory. Broadening this understanding in depth to network design problems outside of the field of phylogenetics may radically change current perspectives on the computational aspects of seamingly unrelated problems as well as information theory and lead to more effective approximate and exact solution algorithms. This research project aims to address this major task, by exploring as comprehensively as possible the combinatorial and optimization aspects of a select few network design problems which share characteristics associated with the BMEP. In particular, this project aims at understanding in depth the connections between information theory, augmentation and routing problems. The project concerns the study of the combinatorics of the Strong Connectivity Augmentation Problem (SCAP) and its connections with the BMEP. Furthermore, we want to pursue a polyhedral approach to study the BMEP, the SCAP and related problems. We want to exploit the new insights that will come out from this study to derive new integer linear programming formulations that are able to solve instances of practical use. Specifically, we want to identify similarities in problems defined on distinct types of networks to specify general notions like permutoassociahedra for different polytopes of network design problems.

We aim to understand the performance of this threshold-based scheduling algorithm. In the first step, we assume that when the scheduling agent switches to a new service mode this is sampled uniformly at random among all possible options. We show that the scheduling algorithm achieves maximum stability and also analyze the mean responses time of the various traffic classes. In the second step, we extend the scheduling agent in order to learn which service mode to use at each queue state.

Supervisors Frits Spieksma (TU/e)
PostDoc Martin Frohn
Location Eindhoven University of Technology (TU/e)


This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement Grant Agreement No 101034253.