在级联范围最大化问题中使用贪婪算法来挑选集合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所能得到的传播效果的百分之多少？

Is the following statement true or false? In the products of methylation-hydrolysis, every -OH group corresponds to the position of a glycosidic bond in the starting polysaccharide.

Which of the follwoing structures represents amylopectin?

Which of the following is true about an aldopentose?I. It is a monosaccharide.II. It contains a CHO groupIII. It is a disaccharide.IV. It is an oligosaccharide.

For stock A, we have 𝛽 𝑖 = 0.70. Suppose the expected market risk premium next year is 9% and the risk-free rate is 3%. What is the expected return of this stock based on the CAPM? (Please answer in % and round to 2 decimal places. If the answer is 8.057%, then in the box, write 8.06)

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单