Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna

Given a metric space on n points, an α-approximate universal algorithm for the Steiner tree problem outputs a distribution over rooted spanning trees such that for any subset X of…