0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ metric ≠ Euclidean. In the metric problem, the input is a distance matrix that might not come from a Euclidean geometry of bounded dimension. $\endgroup$
    – David Eppstein
    Commented May 3, 2013 at 15:16
  • $\begingroup$ 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. $\endgroup$
    – Ramzi Kahil
    Commented May 3, 2013 at 22:05

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.