Recent Developments in Graph Augmentation Problems

Abstract: Augmentation problems are a fundamental class of network design problems. They ask about the cheapest way to increase the (edge-)connectivity of a graph by adding edges among a given set of options. One of the most elementary and intensely studied augmentation problems is the (Weighted) Tree Augmentation Problem. Here, a spanning tree has to be augmented into a 2-edge-connected graph.

Classic techniques for network design yield 2-approximation algorithms for a wide class of augmentation problems. For the Unweighted Tree Augmentation Problem, better-than-2 approximations are known for more than 20 years. However, only recently the first better-than-2 approximations have been found for the more general Unweighted Connectivity Augmentation Problem and Weighted Tree Augmentation Problem. In this talk we will discuss these recent advances.

computational complexitycomputational geometrycryptography and securitydiscrete mathematicsdata structures and algorithmsgame theorymachine learningquantum computing and informationcombinatoricsinformation theoryoptimization and controlprobability

Audience: researchers in the topic

TCS+

Series comments: Description: Theoretical Computer Science

People can register to a talk via our webpage sites.google.com/site/plustcs/livetalk , or subscribe to our calendar and mailing list at sites.google.com/site/plustcs/rss-feeds