1
$\begingroup$

Suppose you have even number of vertices, they form as a complete graph denote the graph by $G$. Now, suppose we compute the minimum weight perfect matching denoted by $P$ (so $P$ has alternating edges, i.e. one is a perfect matching and one is not along all the path $P$ through all vertices of $G$). Now, suppose $T^*$ is TSP tour of $G$.

Show that the inequality is true: $$ \operatorname{cost}(P) \le \min \{ \operatorname{cost}(N_1), \operatorname{cost}(N_2) \},$$

where $N_1$ and $N_2$ are any two perfect matchings on $T^*$.

Note that this inequality from the analysis of Christofides's algorithm, see this nice paper.

$\endgroup$
  • $\begingroup$ The weight of a minimum weight perfect matching is bounded by the weight of any perfect matching, by definition. $\endgroup$ – Yuval Filmus Feb 25 '18 at 13:38
  • $\begingroup$ @YuvalFilmus Ahh I got the idea! I thought that $N_1$ and $N_2$ are only 'two edges' of the tour of TSP. with respect to you Yuval, if you Put your answer in answer section, I will check it! Thank you! $\endgroup$ – user777 Feb 25 '18 at 14:02
1
$\begingroup$

Since $P$ is a minimum weight perfect matching, by definition $$ \operatorname{cost}(P) = \min_N \operatorname{cost}(N), $$ where $N$ goes overl all perfect matchings. In particular, $\operatorname{cost}(P) \leq \operatorname{cost}(N)$ for any particular perfect matching $N$.

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