Abstract
This talk will focus on a graph optimization problem, called the Witness Tree problem, which seeks for a spanning tree of a graph minimizing a certain non-linear objective function. We'll show how this problem plays a crucial role in the analysis of the best approximation algorithms for two fundamental connectivity problems: Steiner Tree and Node-Tree Augmentation.
On the way, I will mention some of Luca's beautiful work on the (in)approximability of some connectivity problems, and share memories of my personal connection with him.