7
$\begingroup$

Questions:

  • Is there some understanding of the reason, why the euclidean TSP allows a PTAS, whereas the metric TSP in general does not and, is the PTAS stable under sufficiently small perturbation of the edge weights of an euclidean TSP?

  • If sufficiently small perturbations of the edge weights do not harm a PTAS, the PTAS can't be tied to euclidicity of the instance and there should be more general conditions for metric TSPs that allow a PTAS; are such conditions known or being investigated?

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ What's a TSP and a PTAS? $\endgroup$
    – Lee Mosher
    Commented Apr 18, 2014 at 13:02
  • 1
    $\begingroup$ @LeeMosher I didn't explain TSP and PTAS because I do not see the danger of confusing interpreting the abreviation as anything else but Traveling Salesman Problem and Polynomial Time Approximation Scheme. $\endgroup$
    – Manfred Weis
    Commented Apr 18, 2014 at 13:10
  • 3
    $\begingroup$ @Manfred: That's a very incorrect assumption. Someone working in your research area might immediately know what you mean by TSP and PTAS, but the majority of the people on MO is not working in your research area... $\endgroup$
    – Tom De Medts
    Commented Apr 18, 2014 at 14:02
  • 1
    $\begingroup$ @TomDeMedts I have the same problem with anything that relates to categories or sheaves and a lot of other things, e.g. the ABC conjecture. My usual reaction is to feed my favorite search engine with the things I don't know and, most of the time I find some papers or wiki articles that provide me with sufficient background information. $\endgroup$
    – Manfred Weis
    Commented Apr 18, 2014 at 14:12
  • 3
    $\begingroup$ The abstract of Arora's original paper says "All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as $\ell_p$ for $p \geq 1$ or other Minkowski norms)." graphics.stanford.edu/courses/cs468-06-winter/Papers/… $\endgroup$
    – usul
    Commented Apr 18, 2014 at 14:17

1 Answer 1

Reset to default
4
$\begingroup$

One of the key ingredients in Arora's proof is the Patching Lemma, which allows you to reduce the number of crossings between subregions while expanding the length of a tour by a controlled amount. An analogue of the Patching Lemma can be proved for more general normed spaces, but not for general metric spaces.

Note, however, that although the Patching Lemma is needed if you want to apply Arora's method "out of the box", Arora himself suggests that the Patching Lemma may not be any kind of intrinsic barrier. Ultimately, there may be no more satisfying "reason" why the general metric TSP does not admit a PTAS beyond the PCP theorem.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ And note that Mitchell independently discovered (about the same time) a PTAS for TSP, based on his guillotine subdivisions: "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems." I cannot myself summarize to what extent his algorithm relies on the Euclidean metric. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 18, 2014 at 23:39
  • $\begingroup$ @Manfred Weis: I should have mentioned this earlier, but you might get a more detailed answer if you post at cstheory.stackexchange.com. $\endgroup$
    – Timothy Chow
    Commented Apr 20, 2014 at 16:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .