PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem Problem 1
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?
Problem 2
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?
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).