青海民族大学学报：教育科学版
青海民族大學學報：教育科學版
청해민족대학학보：교육과학판
Journal of Qinghai Junior Teachers' College
2011年
5期
25-27
,共3页
组合优化问题%下模函数%近似算法%性能保证
組閤優化問題%下模函數%近似算法%性能保證
조합우화문제%하모함수%근사산법%성능보증
combinatorial optimization problem%submodular function%approximation algo-rithm%performance guarantee
下模函数的最值问题在组合优化问题中有着广泛的应用,本文给出了具有均匀拟阵约束下下模函数最大值问题的贪婪近似算法,并讨论了所给算法的性能保证.
下模函數的最值問題在組閤優化問題中有著廣汎的應用,本文給齣瞭具有均勻擬陣約束下下模函數最大值問題的貪婪近似算法,併討論瞭所給算法的性能保證.
하모함수적최치문제재조합우화문제중유착엄범적응용,본문급출료구유균균의진약속하하모함수최대치문제적탐람근사산법,병토론료소급산법적성능보증.
Maximizing submodular function has widely used in combinatorial optimization problem,in this paper,we present an greedy algorithm of maximizing submodular function subject to an maximizing submodular function subject to a even matroid,and discuss its performance guarantee.
