周口师范学院学报
週口師範學院學報
주구사범학원학보
Journal of Zhoukou Normal University
2010年
5期
45~47
,共null页
赵杏利 雷习军 李小平 何尚录
趙杏利 雷習軍 李小平 何尚錄
조행리 뢰습군 리소평 하상록
组合优化 下模集函数 近似算法 性能保证
組閤優化 下模集函數 近似算法 性能保證
조합우화 하모집함수 근사산법 성능보증
combinatorial optimization; submodular set function; approximation algorithm; performance guarantee
给出了在实数范围内求解多背包约束条件下下模集函数最大值问题的一种改进的近似算法,是MaximSviridenko所给出的整数范围内求解单背包约束下下模集函数最大值的扩展.该算法的时间复杂性为：O（kn4）,其性能保证为1-e-1/D.
給齣瞭在實數範圍內求解多揹包約束條件下下模集函數最大值問題的一種改進的近似算法,是MaximSviridenko所給齣的整數範圍內求解單揹包約束下下模集函數最大值的擴展.該算法的時間複雜性為：O（kn4）,其性能保證為1-e-1/D.
급출료재실수범위내구해다배포약속조건하하모집함수최대치문제적일충개진적근사산법,시MaximSviridenko소급출적정수범위내구해단배포약속하하모집함수최대치적확전.해산법적시간복잡성위：O（kn4）,기성능보증위1-e-1/D.
This paper presented an improved approximation algorithm which has performance guarantee of 1-e-1/D in the range of real numbers for the problem of maximizing submodular set function subject to multiple knapsacks constrains.This expended the question in the range of integers of Maxim Sviridenko.Also,this algorithm requires O（kn4） function value computations.
