Algorithms and Computing Systems Series
2026-04-29 13:00 - 14:00 | GH223
Joachim Spoerhase: A Rounding Strategy for Approximating Network Design Problems

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.

https://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1337
