25/09/2025 - CORE B-135

Title: Hardness and Structure in Network Optimization on Unrooted Binary Trees 

Abstract: In this talk, I will explore several properties and complexity results for network optimization problems in the setting of unrooted binary trees. Two main themes will be addressed. First, I will show that strong inapproximability results often arise from highly pathological cases and rarely occur in practical instances. Second, I will revisit the classical connection between optimization and separation, shedding new light on how it applies in this specific context. 

This is joint work with Daniele Catanzaro, Brieuc Pierre, Gwenaël Joret, and Raffaele Pesenti