5 citations · 8 across the 3 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2016★ 1 cited
Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: 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 () relative to an SDP relaxation, wh…
cs.DS2015★ 2 cited
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP
Joe Cheriyan, Zhihan Gao
In Part I, we study a special case of the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. In the special case, we forbid so-called stems; these…
cs.DS2015★ 5 cited
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II
Joe Cheriyan, Zhihan Gao
In Part II, we study the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum~of~Squares) system. We prove that the integrality ratio of an SDP relaxation (the Lasserre…