Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: $1.8+\epsilon$ approximation for (Unweighted) TAP)

Joe Cheriyan, Zhihan Gao

We study the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. We prove an approximation guarantee of ($1.8+\epsilon$) relative to an SDP relaxation, wh…