# Does the Christofides algorithm ensure this inequality?

Let $$(X,d)$$ be a finite metric space. Let $$C$$ be a Hamiltonian cycle (over $$X$$) outputted by Christofide's algorithm. Also, let $$K$$ be a minimum spanning tree. I am aware that Christofide's algorithm is a $$\frac{3}{2}$$ approximation algorithm. But does the following also holds

$$l(C) \le \frac{3}{2} l(K)$$

where $$l(.)$$ denotes the cost, interpreted in a natural way. I do not see why it should hold, but this paper seems to use this as a fact in theorem $$5$$.

• The claim is false for general metric spaces. Take a path on $n$ vertices with unit edge lengths, and $d$ is the shortest path metric induced by this graph. The MST cost is $(n-1)$ while the optimum TSP cost is $2(n-1)$. Apr 22 at 20:52
• The OP does seem to be correct that a line in the proof of Theorem 5 in that paper states that the cycle C has total weight at most (3/2) times the weight of the spanning tree. And Chandra does seem to be right that this doesn't hold in general. So I think OP's question is reasonable. Here is a doi link to the paper: doi.org/10.1007/s003730070012 Apr 23 at 2:39
• Yes, seems like that paper mis-states Christofide's result to be $l(C) \leq (3/2) l(K)$, when the result is only $l(C) \leq (3/2) OPT$ where OPT is the optimal TSP solution.
– usul
Apr 23 at 3:43
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 8, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9692093133926392, "perplexity": 196.40247252854536}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2022-49/segments/1669446711013.11/warc/CC-MAIN-20221205064509-20221205094509-00066.warc.gz"}