<p>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 </p>

CC BY-SA 3.0
2014-01-22T09:12:42.583Z
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$?
Yonatan N
CC BY-SA 3.0
2014-01-22T09:26:43.013Z
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
NicosM
CC BY-SA 3.0
2014-01-22T22:00:47.487Z
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$).
Yonatan N
CC BY-SA 3.0
2014-02-11T09:21:51.693Z
Yes, you are right. We need something like (1-o(1))|E|. Thanks
NicosM
<tsp><approximation>
Asymmetric metric TSP when many edges have equal costs in both directions
NicosM
# Asymmetric metric TSP when many edges have equal costs in both directions

(Asked by: username_0 on 2014-01-22)

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

**Tags:** tsp, approximation
> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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  
> **username_1**: 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$).  
> **username_0**: Yes, you are right. We need something like (1-o(1))|E|. Thanks  

---

## 0 answers

