在级联范围最大化问题中使用贪婪算法来挑选集合S得到的传播效果，至少是最优解SOptimal所能得到的传播效果的百分之多少？

Question

BlackTom AI · Accepted Answer

The greedy algorithm for a monotone submodular objective (such as expected cascade spread) under a cardinality constraint guarantees a (1 - 1/e) approximation to the optimal value.

1) Relevant knowledge points and concepts
- Influence (cascade) spread can be modeled by a set function f(S) that is nonnegative, monotone (adding nodes never decreases spread) and submodular (diminishing returns property).
- Nemhauser et al. (1978) proved that for any nonnegative monotone submodular f and a cardinality constraint k, the greedy algorithm that iteratively adds the element with largest marginal gain achieves at least a (1 - 1/e) fraction of the optimal value.

2) Step-by-step reasoning
- Let OPT = f(S*) be the spread of an optimal seed set S* of size k. Let S_i be the set chosen by the greedy algorithm after i selections, with f(S_0)=0.
- At step i+1, greedy picks an element with marginal gain Δ_greedy ≥ average marginal gain of elements of S* relative to S_i (because it picks the best one).
- By submodularity, the sum of marginal gains of the k elements in S* when added to S_i is at least OPT − f(S_i). Thus the best marginal gain ≥ (OPT − f(S_i))/k.
- Therefore f(S_{i+1}) ≥ f(S_i) + (OPT − f(S_i))/k = (1 − 1/k) f(S_i) + (1/k) OPT.

3) Intermediate calculations
- Rearranging: OPT − f(S_{i+1}) ≤ (1 − 1/k) (OPT − f(S_i)).
- Iterating this inequality k times gives: OPT − f(S_k) ≤ (1 − 1/k)^k · OPT.
- Hence f(S_k) ≥ (1 − (1 − 1/k)^k) · OPT.

4) Why the correct answer is correct
- The limit (1 − (1 − 1/k)^k) is minimized (for integer k≥1) by taking the bound (1 − 1/e) because (1 − 1/k)^k ≤ 1/e. Thus f(S_greedy) ≥ (1 − 1/e) · OPT.
- Numerically 1 − 1/e ≈ 0.6321205588 ≈ 63.2%, i.e., about 63%.

5) Why other options are incorrect
- "Close to 100%": false because greedy is only an approximation; it cannot guarantee full optimality in general.
- "About 50%": too low; the theoretical guarantee is stronger (≈63%).
- "About 37%": this is roughly 1/e ≈ 36.8%, which is the complement of the correct fraction, not the guaranteed achieved fraction.

6) Conclusion
- The greedy selection achieves at least (1 − 1/e) ≈ 63% of the optimal spread. This matches the provided answer: "约63%".

在级联范围最大化问题中使用贪婪算法来挑选集合S得到的传播效果，至少是最优解SOptimal所能得到的传播效果的百分之多少？单项选择题

类似问题

在级联范围最大化问题中使用贪婪算法来挑选集合S得到的传播效果，至少是最优解SOptimal所能得到的传播效果的百分之多少？

You own a bond that pays $64 in interest annually. The face value is $1,000 and the current market price is $1,021.61. The bond matures in 11 years. What is the yield to maturity?

Which of the following statements is CORRECT?

It will cost $9,600 to acquire an ice cream cart that is expected to produce cash inflows of $3,600 a year for three years. After the three years, the cart is expected to be worthless. What is the payback period?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单