12 citations · 30 across the 17 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
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…