Research Institute for Discrete Mathematics

Module "Selected Topics in Discrete Mathematics (V5C2)"

Lecture Course

Approximation Algorithms for Connectivity Augmentation Problems

Winter term 2022/23

Connectivity 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. Classic techniques for network design yield 2-approximation algorithms for a wide class of augmentation problems. However, despite extensive research, for several basic augmentation problems the first better-than-2 approximation algorithms have been found only in the past few years. These recent advances will be the subject of this course.

Course material

  • Introductory Notes: [link]
  • A Better-Than-2 Approximation Algorithm for Weighted Tree Augmentation (Traub, Zenklusen, 2021): [link]
  • Local Search for Weighted Tree Augmentation and Steiner Tree (Traub, Zenklusen, 2021): [link]
  • A talk on the Weighted Tree Augmentation Problem: [link to video] (The talk starts at minute 8:30.)
  • A quick proof for the cactus representation of mincuts (Fleiner, Frank, 2009): [link]
  • A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation (Traub, Zenklusen, 2022): [link]

    Prerequisites: Basic knowledge on graphs and linear programming.
    Time: Thursdays, 4-6 pm
    Room: Seminar room, Lennéstr. 2
    Tentative exam dates: February 13-15 and March 27-28

    V. Traub