Seminar series in Discrete Mathematics and Optimization

The Discrete Mathematics & Optimization seminar occurs at 14:00 on Wednesdays and/or Fridays. It's a chance for the students, staff and friends of DM&O to meet up and discuss research topics from across the group.

If you'd like to give a talk for the seminar, please email .

Talks are normally 30-45 minutes with time for discussion afterwards. You can share your recent research, practice a talk for another event, or simply talk about something you find mathematically interesting :-)

PhD students from EEMCS will receive 1 Graduate School credit from the Graduate School for attending 8 seminars of the series.

05 april 2023 14:00 t/m 15:00

[DMO] Siv Sørensen: Topology reconstruction using time series data in telecommunication networks

We consider Hybrid fiber-coaxial (HFC) networks in which data is transmitted from a root node to a set of customers using a series of splitters and coaxial cable lines that make up a general (non-binary) tree. The physical locations of the components in a HFC network are always known but frequently the cabling is not. This makes cable faults difficult to locate and resolve.

In this study we consider time series data received by customer modems, to reconstruct the topology of HFC networks. We assume that the data can be translated into a series of events, and that two customers sharing many connections in the network will observe many similar events. This approach allows us to use maximum parsimony to minimize the total number of character-state changes in a tree based on observations in the leaf nodes. Furthermore, we assume that nodes located physically close to each other have a larger probability of being connected. Hence, our objective is a weighted sum of data distance and physical distance.

A variable-neighborhood search heuristic is presented for minimizing the combined distance. Furthermore, three greedy heuristics are proposed for finding an initial solution. Computational results are reported for both real-life and synthetic customer data with various degrees of background noise, showing that we are able to reconstruct the topology with a very high precision.