Zobrazeno 1 - 5
of 5
pro vyhledávání: '"Cheriyan, Joe"'
The $k$-Steiner-2NCS problem is as follows: Given a constant $k$, and an undirected connected graph $G = (V,E)$, non-negative costs $c$ on $E$, and a partition $(T, V-T)$ of $V$ into a set of terminals, $T$, and a set of non-terminals (or, Steiner no
Externí odkaz:
http://arxiv.org/abs/2206.11807
Publikováno v:
Mathematical Programming (2019)
We present a $\frac74$ approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS)
Externí odkaz:
http://arxiv.org/abs/1810.07816
Autor:
Cheriyan, Joe, Gao, Zhihan
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, which matches the combinatorial approximation guarantee of Even,
Externí odkaz:
http://arxiv.org/abs/1604.00708
Autor:
Cheriyan, Joe, Gao, Zhihan
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 are a particular type of subtree configuration. For stemless TAP, we
Externí odkaz:
http://arxiv.org/abs/1508.07504
Autor:
Cheriyan, Joe, Gao, Zhihan
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 tightening of an LP relaxation) is $\leq \frac{3}{2}+\epsilon$, where
Externí odkaz:
http://arxiv.org/abs/1507.01309