原书出处
Introduction to Algorithms, Fourth Edition
35 第35章 近似算法
tex cover, and so every edge is covered. Now we consider the weight of the cover. We have
Combining inequalities (35.19) and (35.20) gives w(C) ≤ 2z* ≤ 2w(C*), and hence APPROX-MIN-WEIGHT-VC is a 2-approximation algorithm. ▪ Exercises 35.4-1 Show that even if a clause is allowed to contain both a variable and its negation, randomly setting each variable to 1 with probability 1/2 and to 0 with probability 1/2 still yields
a randomized 8/7-approximation algorithm. 35.4-2 The MAX-CNF satisfiability problem is li
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter035.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea