期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

求解下模福利问题的一种随机算法及其性能保证 被引量：1

A New Randomized Algorithm for Submodular Welfare Problem and Its Performance Guarantee
下载PDF
导出
摘要 给出了求解下模福利问题最大值的一种随机算法,并证明了所给算法的性能保证为1-e-1. A new randomized algorithm for maximizing submodular welfare problem is presented,and that the performance guarantee of this algorithm is 1-e-1 is proved.
作者 李小平 雷习军 赵杏利 何尚录
机构地区 兰州交通大学数理与软件工程学院
出处 《兰州交通大学学报》 CAS 2011年第1期139-141,共3页 Journal of Lanzhou Jiaotong University
关键词 下模福利问题 下模集函数 近似算法 性能保证 submodular welfare problem submodular set function approximation algorithm performance guarantee
分类号 O224 [理学—运筹学与控制论]
  • 相关文献

参考文献8

  • 1Fujishige S. Submodular functions and optimization [M]. New York: North-Holland Press, 2005.
  • 2Vondrak J. Optimal approximation for the submodular welfare problem in the value oracle model[C] // Process of 40th STOC,2008:67-74.
  • 3Lehmann B, Lehmann D, Nisan N. Combinatorial auctions with decreasing marginal utilities [C] // ACM Conference on El. Commerce,2001:18-28.
  • 4Dobzinskl S, Schapira M An improved approximation algorithm for combinatorial auctions with submodular bidders[C]//Process of 17th SODA, 2006:1064-1073.
  • 5Feige U, Vondrak J. Approximation algorithms for combinatorial allocation problems:Emproving the factor of 1-e^-1[C]//Process of 47th FOCS, 2006:667- 676.
  • 6罗亮,贾欣鑫,何尚录.求解组合拍卖问题最大值的贪婪算法[J].黑龙江科技学院学报,2008,18(5):382-384. 被引量：8
  • 7Ageev A,Sviridenko M. Pipage rounding: a new method of constructing algorithms with proven performance guarantee[J]. Journal of Combinatorial Optimization, 2004 (8) : 307-328.
  • 8Nemhauser G L,Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set function- 1 [J ]. Mathematical Programming, 1978, 14 ( 4 ) : 265-294.

二级参考文献7

  • 1SIVIDENKO M I. Wost-case analysis of the greedy algorithm for a generation of the maximum facility location problem[ J ]. Journal of computer and system sciences, 2000, 26 (2) : 193 - 197.
  • 2NENGAYSER G L,WOLSEY L A,FUSGER M L. An analysis of approximations for maximizing submodular set functions-I [ J ]. Mathematical Programming, 1978,14 (4) :265 - 294.
  • 3SVIRIDENKO M. A note on maximizing a submodular set function subject to a knapsack constraint[ J]. Operations Researchi Letters. 2004, 32(3) :41 -43.
  • 4LEHMANN B, LEHMANN D J, NISAN N. Combinatorial auctions with decreasing marginal utilities [ C ]//ACM Conference on EL. Commerce,Tampa, Florida, USA, 2001 : 18 - 28.
  • 5DOBZINSI S, SCHAPIRA M. An improved approximation algorithm for convinatonial auctions with submodular bidders [ C]//Procedings of SODA, Miami, Florida, USA, 2006 : 1064 - 1073.
  • 6李珍,褚衍东,李险峰,张建刚.竖壁自然对流的数值模拟[J].黑龙江科技学院学报,2008,18(1):58-60. 被引量：6
  • 7马文珺,褚衍东,李险峰,张建刚.Rssler混沌同步在保密通信中的应用[J].黑龙江科技学院学报,2008,18(2):140-143. 被引量：2

共引文献7

同被引文献4

引证文献1

二级引证文献1

兰州交通大学学报
2011年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部