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 …

A Better-Than-2 Approximation for Weighted Tree Augmentation Page 1 A Better-Than-2
Approximation for Weighted Tree Augmentation Vera Traub Department of Mathematics ETH …

We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area
of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one …

Connectivity augmentation problems are among the most elementary questions in Network
Design. Many of these problems admit natural 2-approximation algorithms, often through …

The weighted tree augmentation problem (WTAP) is a fundamental network design problem.
We are given an undirected tree G=(V, E) with n=| V| nodes, an additional set of edges L …

The Tree Augmentation Problem (TAP) is a fundamental network design problem in which
we are given a tree and a set of additional edges, also called links. The task is to find a set of …

The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in
the field of network design. Given an undirected tree G=(V, E), an additional set of edges L⊑ …

The basic goal of survivable network design is to build a cheap network that maintains the
connectivity between given sets of nodes despite the failure of a few edges/nodes. The …

The basic goal of survivable network design is to construct low-cost networks which
preserve a sufficient level of connectivity despite the failure or removal of a few nodes or …

Abstract In the Tree Augmentation problem we are given a tree T=(V, F) T=(V, F) and a set E
⊆ V * VE⊆ V× V of edges with positive integer costs {c_e: e ∈ E\} ce: e∈ E. The goal is to …