The ACO Seminar (2026–2027)

In standard network design problems, given an edge-weighted graph, the goal is to find a low-cost subgraph satisfying some connectivity requirements. While many standard NP-hard problems in network design, such as Steiner Tree and Steiner Forest, have small constant factor approximations in undirected graphs, the corresponding problems in directed graphs have strong inapproximability bounds. In this talk, I will talk about a line of recent work showing that these problems (along with extensions to more complex length-bounded settings) admit polylogarithmic approximation factors when the input graph is planar.

The talk is based on joint work with Chandra Chekuri.