1
$\begingroup$

In their article "Double-Tree Approximations for the Metric TSP: Is the Best One Good Enough?", Vladimir Deineko and Alexander Tiskin derive a lower bound for the approximation ratio of the double-tree heuristic (cf e.g. the paper by Vygen http://www.or.uni-bonn.de/~vygen/files/optima.pdf ) by considering a set of points in convex configuration: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=670C2A1BE3622BB312C0440F4162A92A?doi=10.1.1.10.6157&rep=rep1&type=pdf and the approximate solution contains diagonals of the convex hulls.

Question: are there known bounds on the approximation ratio of the double tree heuristic when applied to TSP instances from which edges have been removed that provably can't belong to the optimal solution (most notably the diagonals of the convex hull in the planar euclidean case, or also as described by Jonker and Volgenant "Nonoptimal Edges for the Symmetric Traveling Salesman Problem" or, the generalized graph diagonals as described here: Non-trivial lower bound on the number of "Graph Diagonals")?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.