高级算法—贪心的拟阵分析

status

Published

type

Post

date

Jan 14, 2026

slug

aa-greedy

summary

针对“最大化非负单调次模函数”的问题，证明了在拟阵约束下使用贪心算法可以达到近似比

题目

Problem 2 In class, you learned two greedy algorithms with the same framework:

For maximizing a non-negative additive function over a matroid constraint, the greedy algorithm is exact.

For maximizing a non-negative monotone submodular function under a cardinality constraint, the algorithm gives a -approximation.

Now we consider a common generalization of both problems: given a matroid and a non-negative monotone submodular function , find a set so as to maximize . Consider the same greedy algorithm:

(2a) Prove that the algorithm is a -approximation.

(2b) Show that the approximation ratio of is tight for the algorithm.

Remark: For this problem, a -approximation is also known, so the greedy algorithm is not optimal.

解答

设贪心算法得到的结果为 , 问题的最优解为 , 是拟阵的基. 由于是单调的, 如果不是基, 可以向其中添加元素使其变为基, 而不减少收益, 因此不失一般性假设为拟阵的基.

(2a)

设 , 按照添加顺序, 是贪心算法第步加入的元素, .

设 . 由次模函数的性质, 得:

根据矩阵的 strong basis exchange property, 存在一个到的双射, 对每个 , 有唯一的使得是拟阵的基, 且在贪心算法的第步可选. 但是贪心算法在第步选择 , 因此 , 根据次模函数的性质, , 即 . 代入得:

代入不等式:

因此:

所以贪心算法的近似比为 , 证毕.

(2b)

构造一个符合条件的例子, 使得贪心算法的结果是最优解的 .

设 ground set , 是定义在上的均匀拟阵, 即 .

设为任意小的正数, . 定义函数如下:

显然是非负的, 的单调性和次模性可以使用枚举法证明, 所以该定义满足条件.

在这个例子上运行贪心算法, 算法会在第一步选择 , 在第二步选择或 , 结果的收益为 . 最优解为 , 收益为 , 近似比:

通过调整 , 有 , 因此近似比对于该贪心算法是紧的.

🍵高级算法—贪心的拟阵分析

题目

解答

(2a)

(2b)