<p>Each of the papers shows that there is a polynomial-time approximation scheme (PTAS) for the problem it studies if the input instance is Euclidean and that there is no PTAS if the input instance is arbitrary (if P≠NP).</p>

CC BY-SA 3.0
2013-05-03T13:22:16.680Z
2013-05-03T14:06:07.083Z
2013-05-03T14:06:07.083Z
Yury
<h1>Problem 1</h1>
<p>I have read &quot;On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem&quot; (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements &quot;We present a polynomial time approximation scheme for Minimum-Cost k-Connected subgraph problem&quot; and in the second paragraph of the abstract they state that there is no PTAS unless P=NP. I am sure there is a small difference between the tow problems, but I cannot see what it is. Could someone clarify for me what problem does not have a PTAS and how its different from the problem in the first paragraph of the abstract?</p>
<h1>Problem 2</h1>
<p>Because I didn't really get the paper from the first problem, I read &quot;Polynomial Time Approximation Scheme from Euclidean TSP and other Geometric Problems&quot; (by S. Arora), and I have the same problem here, he claims to give a PATS for euclidean TSP, but in the intro states &quot;[...] showed that if P≠NP then metric TSP and many other problems do not have a PTAS&quot;. I see there some kind of contradiction, they are giving a PTAS, but say that some showed that there cannot be any. What am I missing?</p>

CC BY-SA 3.0
2013-05-03T15:16:43.370Z
metric ≠ Euclidean. In the metric problem, the input is a distance matrix that might not come from a Euclidean geometry of bounded dimension.
David Eppstein
CC BY-SA 3.0
2013-05-03T22:05:05.563Z
Thanks, I have understood it the wrong way. I thought they mean that every metric space (which includes the Euclidean space) has no PTAS for TSP.
Ramzi Kahil
<graph-theory><np-hardness><approximation-algorithms><tsp>
PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem
Ramzi Kahil
# PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

(Asked by: username_0 on 2013-05-03)

# Problem 1

I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time approximation scheme for Minimum-Cost k-Connected subgraph problem" and in the second paragraph of the abstract they state that there is no PTAS unless P=NP. I am sure there is a small difference between the tow problems, but I cannot see what it is. Could someone clarify for me what problem does not have a PTAS and how its different from the problem in the first paragraph of the abstract?

# Problem 2

Because I didn't really get the paper from the first problem, I read "Polynomial Time Approximation Scheme from Euclidean TSP and other Geometric Problems" (by S. Arora), and I have the same problem here, he claims to give a PATS for euclidean TSP, but in the intro states "[...] showed that if P≠NP then metric TSP and many other problems do not have a PTAS". I see there some kind of contradiction, they are giving a PTAS, but say that some showed that there cannot be any. What am I missing?

**Tags:** graph-theory, np-hardness, approximation-algorithms, tsp
> **Comments:**
> **username_1**: metric ≠ Euclidean. In the metric problem, the input is a distance matrix that might not come from a Euclidean geometry of bounded dimension.  
> **username_0**: Thanks, I have understood it the wrong way. I thought they mean that every metric space (which includes the Euclidean space) has no PTAS for TSP.  

---

## 1 answers

### Answer by username_2 on 2013-05-03. Score: 3 | Accepted answer

Each of the papers shows that there is a polynomial-time approximation scheme (PTAS) for the problem it studies if the input instance is Euclidean and that there is no PTAS if the input instance is arbitrary (if P≠NP).


---

