A Rounding Strategy for Approximating Network Design Problems

29^th April 2026, 13:00 GH223
Joachim Spoerhase
University of Liverpool

Abstract

A classic approach to design approximation algorithms for NP-hard network design problems such as the travelling salesman problem (TSP) or Steiner tree is to identify a (usually simple) combinatorial structure that approximates the hard problem. I will discuss an algorithmic strategy to improve upon the resulting (sometimes long-standing) bounds. The idea is to reduce the cost of the combinatorial structure by combining it with a randomly sampled structure extracted from a linear-programming relaxation. I will give a (high-level) overview on how this approach has been applied to Steiner tree and TSP to give the currently best approximation algorithms. I will also discuss a related recent work of mine (jointly with Martin Böhm, Zachary Friggstad, and Tobias Mömke) on variants of TSP.