approximation ratio of TSP problem where the weights are bounded by an inequality

Question

Consider a variant of the TSP problem where the cost function $c$ is not only symmetric but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a polynomial time algorithm that achieves a constant factor approximation ratio for this problem.

I think the algorithm itself is the same as the one with the triangle inequality where we find an MST, but I'm not sure about what the approximation ratio would be for this problem?

Answer 1

Summary: Start with a minimum spanning Tree (MST). Then modify it slightly to a Hamiltonian circuit.

Mini-step traversal of $(T,s)$

Let $T$ be a tree.

Definitions: For two vertices $u$ and $v$, let $d(u,v)$ be the number of edges in the unique path from $u$ to $v$.
A sequence $v_1, v_2, \cdots, v_n$ is called a mini-step traversal of $(T, s)$ if

• it is a permutation of all vertices in $V$, and
• $v_1=s$, and
• $d(v_i, v_{i+1})\le 3$ for all $i$ such that $1\le i\lt n$, and
• $d(v_n, v_1)= 1$ if $n\gt1$, and
• if we walk from $v_1$ to $v_2$, then to $v_3$, and so on to $v_n$, and back to $v_1$, always along the unique path between the vertices, then we will walk over any edge of $T$ at most $2$ times.

Claim. Let $s\in V$. There is a mini-step traversal of $(T, s)$.
Proof: Use induction on $n = |V|$.
The base case, when $n=1$ is trivial.
Consider the case of $n\ge2$. As induction hypothesis, assume the claim is true for smaller $n$.
Let $u_1, \cdots, u_k$ be the neighborhood of $v$. If we remove $s$ from $T$, $T$ will be split into $k$ trees, which will be denoted by $T_1, \cdots, T_k$, where $T_i$ is the tree that contains $u_i$.
Thanks to induction hypothesis, let $v_{1,i}, v_{2,i}, \cdots, v_{n_i, i}$ be a mini-step traversal of $(T_i, u_i)$. Then we can verify that $s, v_{1,1}, v_{2,1}, \cdots, v_{n_1, 1}, v_{1,2}, v_{2,2}, \cdots, v_{n_2, 2},\cdots, v_{1,k}, v_{2,k}, \cdots, v_{n_k, k}$ is a mini-step traversal of $(T,s)$. $\quad\checkmark$

Note that the proof provides an $O(n^2)$-time algorithm to construct a mini-step traversal of $(T,s)$, given tree $T$ with $n$ vertices and vertex $s$.

A polynomial-time algorithm

Input: A complete graph $G$ and a symmetric cost function $c$ that satisfies $0\le c(u,v)\le2c(u,w)+c(w,v)$
Output: a Hamiltonian circuit of $G$
Procedure:

1. Obtain an MST of $G$, which is denoted by $M$.
2. Let $s$ be a vertex in $M$. Obtain a mini-step traversal of $(M,s)$.
3. Return that traversal as a Hamiltonian circuit, denoted by $\mathcal C$.

Approximation ratio $\frac72$

Claim: $c(\mathcal C)\le\frac72\,min\_cost$, where $min\_cost$ is the minimum cost of a Hamiltonian circuit of $G$.
Proof: Since $c(M)\le min\_cost$, it is enough to prove $c(\mathcal C)\le\frac72c(M)$.
Suppose $C=(v_1, v_2, \cdots, v_n, v_{n+1}=v_1)$. $$\begin{aligned} c(\mathcal C) &=\sum_{1\le i\le n}c(v_i, v_{i+1})\\ &\le\sum_{1\le i\le n}\left(\frac74\sum_{e\in {\text{the unique path in }M\text{ from }v_i\text{ to }v_{i+1}}}c(e)\right)\\ &=\frac74\sum_{1\le i\le n}\ \sum_{e\in {\text{the unique path in }M\text{ from }v_i\text{ to }v_{i+1}}}c(e)\\ &\le\frac74\sum_{e\in M}2c(e)\\ &=\frac72c(M) \end{aligned}$$ where the last inequality is the last property of a mini-step traversal, while the first inequality comes from the inequalities below since $d(v_i, v_{i+1})\le3$ with respect to $M$.

• for any vertex $u,v,w$, we have $c(u, v) \le\frac32(c(u, w) + c(w, v))$
  Proof: $c(u, v) \le 2c(u, w) + c(w, v)$. Switching $u$ and $v$, we also have $c(v, u) \le 2c(v, w) + c(w, u)$. Note that $c(v, u)=c(u,v)$, $c(v, w)=c(w,v)$, $c(w,u)=c(u,w)$. Adding both inequalities, we are done.
• for any vertex $u,v,w,x$, we have $c(u, v) \le\frac74(c(u, w) + c(w, x) + c(x,v))$
  Proof: $c(u, v)\le 2c(u,w) + c(w,v)\le2c(u,w) + \frac32(c(w,x)+c(x,v))$. Similarly, $c(u, v)\le\frac32(c(u,w)+c(w,x)) + 2c(x,v)$. Add both inequalities.