<p>Given a graph <span class="math-container">$G=(V,E)$</span>, costs <span class="math-container">$c \in \mathbb{R}^E$</span> the TSP problem is to compute a min cost tour of the graph. The LP is</p>
<p>min <span class="math-container">$ c^tx  $</span></p>
<p><span class="math-container">$x(\delta(S)) \geq 2  \ \ \ \ \forall S \subset V  $</span></p>
<p><span class="math-container">$x(\delta(v))=2 \ \ \ \ \ \forall v \in V $</span></p>
<p><span class="math-container">$x \geq 0$</span></p>
<p>The standard LP gap example for the held karp relaxation  for TSP
Is to have two triangles and three long paths connecting the corresponding vertices yielding a 4/3 integrality gap example.</p>
<p><a href="https://i.sstatic.net/kB9JD.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kB9JD.png" alt="4/3 gap example   https://kintali.wordpress.com/2009/07/03/held-karp-relaxation/" /></a></p>
<p>Does this not work for Euclidean TSP?  I saw this paper here  [2014] <a href="https://www.sciencedirect.com/science/article/abs/pii/S0167637714001205" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/abs/pii/S0167637714001205</a></p>
<p>Indicating the previous known gap was 8/7 instead.</p>

CC BY-SA 4.0
2022-02-25T15:57:17.720Z
Do you have some specific embedding of the two-triangle graph in a Euclidean metric in mind?  Surely it won't work for all embeddings.  Note that Euclidean graphs are complete graphs, etc.  Also, for the reader, can you fully specify the LP?  You haven't said what $S$ and $v$ range over, what the specific variables are, nor what the notation $x(...)$ represents.
Neal Young
CC BY-SA 4.0
2022-02-25T16:47:23.707Z
The canonical 4/3 integrality gap example contains three parallel paths that are very costly to move between, e.g. the vertices in the centers of those paths are roughly at distance $n$ despite the obvious plane embeddings giving them pairwise distance $O(1)$. So, for example, if we consider the embedding where the vertices fall on the 3 × n grid, [a Euclidean tour can cheaply zigzag between two such paths in one direction and return using the third path](https://i.imgur.com/epOisHu.jpg), with cost close to LP-OPT. Do you have a specific embedding in mind that you imagine can cause problems?
Yonatan N
CC BY-SA 4.0
2022-02-26T00:10:37.003Z
@YonatanN  what if you made the points denser on the paths?  The zigzagging only works if the distance between 2 points on the paths is the same as the vertical distance so just make the points on each of the 3 paths close together and zigzagging doesn't work anymore.
Hao S
CC BY-SA 4.0
2022-02-27T23:36:49.413Z
Hao, why not describe in your post the entire argument you have in mind, step by step?  As far as I can tell your suggestion can work, but I think it would better for you to post a full proof so people can check it.  Also, you might want to contrast your argument with the argument for the 4/3 gap (in the Euclidean case) in the 2014 paper you link to.
Neal Young
<co.combinatorics><optimization><integer-programming><integrality-gap>
Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?
Hao S
# Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?

(Asked by: username_0 on 2022-02-25)

Given a graph $G=(V,E)$, costs $c \in \mathbb{R}^E$ the TSP problem is to compute a min cost tour of the graph. The LP is

min $ c^tx $

$x(\delta(S)) \geq 2 \ \ \ \ \forall S \subset V $

$x(\delta(v))=2 \ \ \ \ \ \forall v \in V $

$x \geq 0$

The standard LP gap example for the held karp relaxation for TSP
Is to have two triangles and three long paths connecting the corresponding vertices yielding a 4/3 integrality gap example.

[![4/3 gap example   https://kintali.wordpress.com/2009/07/03/held-karp-relaxation/](https://i.sstatic.net/kB9JD.png)](https://i.sstatic.net/kB9JD.png)

Does this not work for Euclidean TSP? I saw this paper here [2014] <https://www.sciencedirect.com/science/article/abs/pii/S0167637714001205>

Indicating the previous known gap was 8/7 instead.

**Tags:** co.combinatorics, optimization, integer-programming, integrality-gap

> **Comments:**
> **username_1**: Do you have some specific embedding of the two-triangle graph in a Euclidean metric in mind?  Surely it won't work for all embeddings.  Note that Euclidean graphs are complete graphs, etc.  Also, for the reader, can you fully specify the LP?  You haven't said what $S$ and $v$ range over, what the specific variables are, nor what the notation $x(...)$ represents.  
> **username_2**: The canonical 4/3 integrality gap example contains three parallel paths that are very costly to move between, e.g. the vertices in the centers of those paths are roughly at distance $n$ despite the obvious plane embeddings giving them pairwise distance $O(1)$. So, for example, if we consider the embedding where the vertices fall on the 3 × n grid, [a Euclidean tour can cheaply zigzag between two such paths in one direction and return using the third path](https://i.imgur.com/epOisHu.jpg), with cost close to LP-OPT. Do you have a specific embedding in mind that you imagine can cause problems?  
> **username_0**: @YonatanN  what if you made the points denser on the paths?  The zigzagging only works if the distance between 2 points on the paths is the same as the vertical distance so just make the points on each of the 3 paths close together and zigzagging doesn't work anymore.  
> **username_1**: Hao, why not describe in your post the entire argument you have in mind, step by step?  As far as I can tell your suggestion can work, but I think it would better for you to post a full proof so people can check it.  Also, you might want to contrast your argument with the argument for the 4/3 gap (in the Euclidean case) in the 2014 paper you link to.  

---

## 0 answers

