1 citations · 1 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2014
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou +1
We study the ATSP (Asymmetric Traveling Salesman Problem), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result…
cs.DS2014
On the metric s-t path Traveling Salesman Problem
Zhihan Gao
We study the metric - path Traveling Salesman Problem (TSP). [An, Kleinberg, and Shmoys, STOC 2012] improved on the long standing -approximation factor and prese…
cs.DS2013★ 1 cited
An LP-based 3/2-approximation algorithm for the graphic s-t path TSP
Zhihan Gao
We design a new LP-based algorithm for the graphic - path Traveling Salesman Problem (TSP), which achieves the best approximation factor of 1.5. The algorithm is based on the…