A ranking model for the greedy algorithm and discrete convexity
A ranking model for the greedy algorithm and discrete convexity
复制标题
贪心算法和离散凸性的排序模型
DOI：
10.1007/s10107-010-0406-2
复制
发表时间：
2012
影响因子：
2.7
通讯作者：
Britta Peis
中科院分区：
文献类型：
--
作者：
U. Faigle;W. Kern;Britta Peis
推广集合函数的Lovász扩展和离散Choquet积分的思想，我们引入一个组合模型，使我们能够定义和分析拟阵型贪婪算法。该模型是基于一个实值函数V上的（有限）家庭的集合，产生的组合线性规划的约束。此外，v给出了基集N的元素的排序和选择过程，因此意味着线性规划的贪婪算法。证明了贪婪算法保证产生原始和对偶最优解的充要条件是$${\mathbb{R}^N}$$上的一个相关泛函是凹的。以前的拟阵型贪婪模型，以适应目前的一般情况。特别地，给出了超模约束下组合优化问题的一般模型，保证了贪婪算法的有效性。
Generalizing the idea of the Lovász extension of a set function and the discrete Choquet integral, we introduce a combinatorial model that allows us to define and analyze matroid-type greedy algorithms. The model is based on a real-valued function v on a (finite) family of sets which yields the constraints of a combinatorial linear program. Moreover, v gives rise to a ranking and selection procedure for the elements of the ground set N and thus implies a greedy algorithm for the linear program. It is proved that the greedy algorithm is guaranteed to produce primal and dual optimal solutions if and only if an associated functional on $${\mathbb{R}^N}$$ is concave. Previous matroid-type greedy models are shown to fit into the present general context. In particular, a general model for combinatorial optimization under supermodular constraints is presented which guarantees the greedy algorithm to work.