2
$\begingroup$

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/

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Feb 25, 2022 at 15:57
  • $\begingroup$ 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, with cost close to LP-OPT. Do you have a specific embedding in mind that you imagine can cause problems? $\endgroup$
    – Yonatan N
    Commented Feb 25, 2022 at 16:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – Hao S
    Commented Feb 26, 2022 at 0:10
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Feb 27, 2022 at 23:36

0

Reset to default

Your Answer

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