3 citations · 10 across the 13 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021★ 1 cited
Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
Fabrizio Grandoni, Afrouz Jabal Ameli, Vera Traub
The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A cele…
cs.DS2021
Local Search for Weighted Tree Augmentation and Steiner Tree
Vera Traub, Rico Zenklusen
We present a technique that allows for improving on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. Relative greedy procedures are a particu…
cs.DS2021
A Better-Than-2 Approximation for Weighted Tree Augmentation
Vera Traub, Rico Zenklusen
We present an approximation algorithm for Weighted Tree Augmentation with approximation factor . This is the first algorithm beating the longstanding f…