Bundit Laekhanukit, Shanghai University of Finance and Economics

Abstract

In the directed Steiner tree problem, we are given an edge-weightedgraph G, a root r, and a set of terminals K. The goal is to find a minimum-cost subgraph of G that connects the root r to every terminal in K. This talk discusses recent progress on approximation algorithms and hardness results for this challenging problem. We will also share a few insights that remain less widely known, highlighting areas where further exploration may prove fruitful.

See: https://theory.cs.rutgers.edu/theory_seminar