Please note: This seminar will take place in DC 1304 and online.

Nathan Klein, Assistant Professor
Department of Computer Science, Boston University

In the weighted tree augmentation problem (WTAP) we are given a tree T and a set of weighted edges called links. The goal is to select a minimum weight set of links to add to the tree so that it becomes 2-edge-connected. This is a classic NP-Hard network design problem: phrased another way, it asks to increase the edge fault tolerance of a tree from 0 to 1.

Until the recent exciting work of Traub and Zenklusen, which culminated in a local-search based 1.5+epsilon approximation in 2023, it was unknown whether it was possible to beat a factor of 2 for WTAP. In this talk, I will discuss a 1.49 approximation algorithm obtained by rounding a strong LP relaxation. This goes below the integrality gap of 1.5 of the cut LP, a standard relaxation for WTAP, and is the first LP-based algorithm to get a factor below 2. The LP we round is similar to the standard one strengthened with constantly many rounds of Sherali-Adams, however we add additional constraints to help control its behavior.

Based on join work with Vincent Cohen-Addad, Marina Drygala, and Ola Svensson

To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.