知识卡片

普通读书笔记卡 · 3718.c

旅行商无三角约束难近似

理解等级:高级

若一般旅行商存在任意固定近似比ρ的多项式算法,就可把哈密顿环实例补成完全图,原边费用1、非原边费用设为足够大的惩罚值。

原图有环时最优费用为|V|,无环时所有行程费用都跨越ρ倍缺口,从算法输出即可判定哈密顿环;除非P=NP,否则该近似算法不存在。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第35章 近似算法 · 查看原书依据

      Convert G into an instance of the traveling-salesperson problem as follows. Let G′ = (V, E′) be the complete graph on V, that is, E′ = {(u, v) : u, v ∈ V and u ≠ v}. Assign an integer cost to each edge in E′ as follows: Given a representation of G, it takes time polynomial in |V| and |E| to create representations of G′ and c. Now

    参考来源

    - 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[20000,25000))。 - 结论依据:第35章无三角约束旅行商、集合覆盖与随机近似、线性松弛的原文论证;图35.3已核对。 - 原始内容:Convert G into an instance of the traveling-salesperson problem as follows. Let G ′ = ( V , E ′) be the complete graph on V , that is, E ′ = {( u , v ) : u, v ∈ V and u ≠ v }. Assign an integer cost to each edge in E ′ as follows: Given a representation of G , it takes time polynomial in | V | and | E | to create representations of G ′ and c . Now