0
$\begingroup$

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

$\endgroup$
4
  • 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, 2014 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, 2014 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, 2014 at 22:00
  • $\begingroup$ Yes, you are right. We need something like (1-o(1))|E|. Thanks $\endgroup$
    – NicosM
    Feb 11, 2014 at 9:21

0

Your Answer

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

Browse other questions tagged or ask your own question.