I would like to ask whether there exists a better approximation result on a special case of the ATSP metric instances: when cost(a,b)=cost(b,a) for $O(log(|E|)$ edges, or something close/related to that (in fact when this holds for the 'small-cost' edges). Thank you

  • 1
    $\begingroup$ I think this needs to be worded more carefully. What's stopping you from taking a standard ATSP instance and replacing a vertex with a clique of size $O(\sqrt{\log n})$ with all inner-distances $\epsilon$? $\endgroup$ – Yonatan N Jan 22 '14 at 9:12
  • $\begingroup$ It should be worded better. Assume that there exist $|V|/2$ distinct pairs of vertices with symmetric 'small costs' (i.e. these are the $|V|/2$ smaller edge costs of the graph). I did not want initially to be more specific, thats why I asked for a close/related result. Thanks $\endgroup$ – NicosM Jan 22 '14 at 9:26
  • 1
    $\begingroup$ You still end up with the same problem in that case, as can be seen by replacing every vertex with a length-2 path with distance $\epsilon$. I can't imagine the problem becomes much easier without having something like $(1-o(1))|E|$ symmetrical edges, as replacing each vertex of the graph with a sufficiently large $\epsilon$-distance clique pads the count of small, symmetrical edges without changing the problem significantly (for small enough $\epsilon$). $\endgroup$ – Yonatan N Jan 22 '14 at 22:00
  • $\begingroup$ Yes, you are right. We need something like (1-o(1))|E|. Thanks $\endgroup$ – NicosM Feb 11 '14 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.