Heuristic Algorithms for Steiner Tree Problem

Speaker:

Xinyu Wu (University of Electronic and Science Technology of China)

Time:

10:00-11:00 (Time in Beijing)
14:00-15:00 (Time in Auckland)
September 3, 2021 (Friday)

VooVmeeting:

Link: https://meeting.tencent.com/dm/WlulUnrGJ0NM?rs=25

ID: 969 615 091

Venue:

Qingshuihe Campus

Abstract:

The Steiner tree problem (STP) is a challenging NP-hard problem that commonly arises in practical applications as one of many variants. We will introduce the STP problem and the solving algorithms including several reduction tests and 4 effective operators which are wildly used in most heuristic algorithms. Among all heuristic algorithms, PUW performs best in experiments. But It performs not so well on some large graphs. We found that partitioning the large graph into subgraphs to solve separately may bring better solutions. So we aim to solve the large graph by a heuristic partitioning algorithm, Multi-Level. Some results show that our approach is effective. We will study and improve the Multi-level framework and experiments in the future.