1
$\begingroup$

Input: complete, undirected graph $G=(V,E)$ and cost function $c$ Assume for all nodes $x,y,z \in V$: $c(x,z)\le c(x,y) + 100\cdot c(y,z)$

Find a 200-approximation polynomial time algorithm for the input.

I've seen the regular 2-approximation algorithm for a graph that satisfies the triangle inequality.

  1. Find the MST $T$ for the graph
  2. Find Euler Cycle by doubling the edges in $T$
  3. Find Hamiltonian Cycle by removing each vertex that appears more than once

If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$ , so I figure we can use the same approximation algorithm. But I'm not sure how to prove that this gives a 200-approximation.

$\endgroup$
1
$\begingroup$

This is not true.

If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$

However it is true that, for $x,z \in V$ with $x \neq z$, you have $c(x,z) \le 100 d(x,z)$. To see this let $P$ be a shortest path from $x$ to $z$. The proof is by induction on the number of edges $|P|$ of $P$.

If $|P|=1$ then $c(x,z) = d(x,z) \le 100 d(x,z)$.

If $|P| \ge 2$ then, let $y$ be the vertex immediately preceding $z$ in $P$. By inductive hypothesis $c(x, y) \le 100 d(x,y)$ and you have $$ c(x,z) \le c(x,y) + 100 c(y,z) \le 100 d(x,y) + 100 c(y,z) =100 d(x,z). \quad \square $$

Consider a MST $M$ of $G$ and let $T$ be a Euler tour of $M$, starting from an arbitrary vertex. Let $v_0, v_1, \dots, v_{n-1}$ be the vertices in $V$ in the order they appear for the first time in $T$ and let $v_n = v_0$. Consider the tour $T'$ that visits $v_0, v_1, \dots, v_n$ in this order.

For $i=0, \dots, n-1$ let $T_i$ be the portion of the tour between the first occurrence of $v_i$ in $T$ and the next occurrence of $v_{i+1}$ in $T$. Given any graph $H$, let $c(H)$ be the sum of costs of the edges in $H$. Let $T^*$ an optimal tour of $G$.

You have: $$ \begin{align*} c(T') &= \sum_{i=0}^{n-1} c(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} d(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} c(T_i) \\ &\le 100 c(T) \le 200 c(M) \le 200 c(T^*). \end{align*} $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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