A (1+ln2)(1+ln2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
A (1+ln2)(1+ln2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
Nachshon Cohen,Zeev Nutov
2013 · DOI: 10.1016/j.tcs.2013.04.004
Theoretical Computer Science · 34 Citations
TLDR
A ( 1 + ln 2 ) -approximation algorithm for trees of constant radius is given, based on a new decomposition of problem feasible solutions, and on an extension of Steiner Tree technique of Zelikovsky to the Set-Cover problem, which may be of independent interest.