A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing

Guy Kortsarz

The \emph{Tree Augmentation Problem (TAP)} is given a tree $T=(V,E_T)$ and additional set of {\em links} $E$ on $V\times V$, find $F\subseteq E$ such that $T\cup F$ is $2$-edge-c…