2
$\begingroup$

The Prize-Collecting TSP (PCTSP) is defined as the ordinary TSP with the difference that penalties are added to nodes; so we may avoid visiting a node paying its penalty, which is added to the overall cost. It currently admits a $2-\epsilon$ approximation ratio, where edge costs are considered to satisfy the triangle inequality. Obviously, ordinary TSP is PCTSP where all node penalties are set to inf.

I would like to ask, in the case a graph which does not satisfy the triangle inequality is chosen and ALL of its edges are deleted, replaced by 2 new edges connected to a 2-degree new node for each case of deleted edge, where each edge cost is equal to the deleted edge's cost/2 and having Euclidean distance equal to that (so the new graph is metric), don't we get a $(2-\epsilon)$ approximation ratio for the original (general and therefore non-approximable) graph? (Penalties for old nodes are set to inf and to new 2-degree nodes equal to 0).

Of course, there is a mistake in my thought, since this can't be true, so if somebody finds it, I would be pleased to listen to that. Thank you in priori.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ It would be nice if you add a motivation part to your question and explain why you are interested in this question. $\endgroup$
    – Kaveh
    Apr 18, 2011 at 8:27
  • 1
    $\begingroup$ @Kaveh: Because it would prove that P = NP... $\endgroup$
    – 5501
    Apr 18, 2011 at 10:38
  • 1
    $\begingroup$ @5501 that's not a motivation for this particular question. One of the aspects of writing good questions is explaining why you care about the question. $\endgroup$
    – Suresh Venkat
    Apr 18, 2011 at 16:01
  • 1
    $\begingroup$ Well I think it is obvious that I did not try to solve P=NP initially... $\endgroup$
    – N27
    Apr 18, 2011 at 18:51
  • 1
    $\begingroup$ I just read a paper on PCTSP and have the curiosity on this issue, which continues to stay unexplained to me, btw. But, obviously, there is a flaw somewhere in my thought. $\endgroup$
    – N27
    Apr 19, 2011 at 20:30

1 Answer 1

Reset to default
1
$\begingroup$

Edited may answer, I hope it becomes clearer now (or I find out what I did not understand):

Your process is as follows: If you have an edge $e = \{u,v\}$ with weight $t$ you replace $e$ by a path of length two with edges $\{u,z_e\}$ and $\{z_e,v\}$. $z_e$ is a new node and each of the two new edges get weight $t/2$. For each edge, we introduce a new node.

So far, we do not have a metric instance, because there is no edge between $u$ and $v$ so far and the distance between $u$ and $v$ is infinite. Therefore, you take the shortest path metric to get these distances. (I suppose that this is what you mean by "having Euclidean distances equal to that". Otherwise, you should clarify this.)

My point is that after adding distances according to the shortest path metric, the distance between $u$ and $v$ might not be $t$ anymore, so you do not get your original instance back: Consider a triangle with edge lengths $1$, $1$ and $t$. Let $u$ and $v$ be the nodes of the edge with weight $t$. Apply your construction. The shortest path between $u$ and $v$ is $2$ (it takes the four edges with weight $1/2$) and not $t$.

Btw: Euclidean distance should just be distance in the question.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am not saying that. The 2 new edges have each cost t/2 but their costs are exactly equal to their distances. In other words, doing that for each one of the 3 triangle edges, creates a cycle of 6 vertices, where no 2 edges having a common endpoint are parallel to each other and where each edge's cost is equal to the edge's length. Or maybe I have misunderstood your statement and your talking about something else.. $\endgroup$
    – N27
    Apr 18, 2011 at 11:15
  • $\begingroup$ But if you now take the metric completion, the shortest path from u to v does not take the two edges with weight t/2 but the four edges with weight 1/2. So you do not get your original graph back. $\endgroup$
    – 5501
    Apr 18, 2011 at 11:48
  • $\begingroup$ Maybe you did not understand what I am trying to do in my original question or I do not understand what you are trying to say. Anyway..! And also, what is a metric completion of a graph? I googled that and I get no results. $\endgroup$
    – N27
    Apr 18, 2011 at 18:50
  • $\begingroup$ Tried to clarify my answer. I used "metric completion" as a synoymn for "taking the shortest path metric". Or don't you do that after subdividing edges? $\endgroup$
    – 5501
    Apr 18, 2011 at 19:09

Your Answer

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

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