摘要
研究了求解预支约束下批发零售问题的一种新的近似算法,这一算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法相结合并从理论上分析了该算法的可靠性和有效性,最后得出了该算法的性能保证为1-e-1.
A new approximation algorithm is presented for wholesale-retail problem.The algorithm is an improved greedy algorithm which combines the part of enumeration method with the greedy algorithm.At the same time,the reliability and effect of this algorithm are theoretically proved.Finially,it is presented that the algorithm has 1-e-1 performance guarantee for this problem.
出处
《兰州交通大学学报》
CAS
2009年第6期138-140,共3页
Journal of Lanzhou Jiaotong University
关键词
预支约束
下模函数
近似算法
性能保证
budgeted constraint
submodular function
approximation algorithm
performance guarantee
