知识卡片

普通读书笔记卡 · 3716.b.1.a

近似证明可借最优下界

理解等级:高级

证明近似比不必计算未知的最优值,可以找一个易求的最优下界L,再证明算法结果不超过ρL。

顶点覆盖的被选边构成极大匹配,匹配大小就是覆盖规模下界;需区分极大匹配与最大匹配。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The size of a maximal matching is, as we argued in the proof of Theorem 35.1, a lower bound on the size of an optimal vertex cover. The algorithm returns a vertex cover whose size is at most twice the size of the maximal matching A. The approximation ratio comes from relating the size of the solution returned to the lower bound. We will use this

    参考来源

    - 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[10000,15000))。 - 结论依据:第35章近似定义、顶点覆盖与满足三角不等式的旅行商算法;图35.1–35.2已核对。 - 原始内容:The size of a maximal matching is, as we argued in the proof of Theorem 35.1, a lower bound on the size of an optimal vertex cover. The algorithm returns a vertex cover whose size is at most twice the size of the maximal matching A . The approximation ratio comes from relating the size of the solution returned to the lower bound. We will use this