# 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?

• metric ≠ Euclidean. In the metric problem, the input is a distance matrix that might not come from a Euclidean geometry of bounded dimension. May 3, 2013 at 15:16
• 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. May 3, 2013 at 22:05

## 1 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).