ANALYSIS OF APPROXIMATIONS FOR MAXIMIZING SUBMODULAR SET FUNCTIONS .1.
ANALYSIS OF APPROXIMATIONS FOR MAXIMIZING SUBMODULAR SET FUNCTIONS .1.
复制标题
DOI：
10.1007/bf01588971
复制
发表时间：
1978-01-01
影响因子：
2.7
通讯作者：
FISHER, ML
中科院分区：
文献类型：
--
作者：
NEMHAUSER, GL;WOLSEY, LA;FISHER, ML
设N是有限集，z是定义在N的子集集上的实值函数，对所有S，TinN，满足z（S）+z（T）≥z（S <$T）+z（S <$T），这样的函数称为次模函数.我们考虑问题maxS <$N{a（S）：|S| ≤K，z（S）submodular}.在此框架下可以提出几个组合优化问题.例如，在拟阵中寻找最大权独立集的问题，当拟阵的元素是着色的并且独立集的元素不能超过K个颜色时，就属于这一类。无容量限制的选址问题是该拟阵优化问题的一个特例，我们分析了该问题的贪婪算法和局部改进算法，并给出了一个线性规划松弛算法。我们的结果是最坏情况下的近似质量的界限。例如，当z（S）不减且z（0）= 0时，我们证明了“贪婪”启发式算法总是产生一个解，其值至少是最优值的1-[（K-1）/K] K倍。这个界限可以对每一个K都达到，并且有一个极限值（e − 1）/e，其中e是自然对数的底。
LetNbe a finite set andzbe a real-valued function defined on the set of subsets ofNthat satisfies z(S)+z(T)≥z(S⋃T)+z(S⋂T) for allS, TinN.Such a function is called submodular. We consider the problem maxS⊂N{a(S):|S|≤K,z(S) submodular}.Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanKcolors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S)is nondecreasing andz(0) = 0, we show that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1)/K]Ktimes the optimal value. This bound can be achieved for eachKand has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.