On a posterior evaluation of a simple greedy method for set packing
On a posterior evaluation of a simple greedy method for set packing
复制标题
DOI：
10.1007/s11590-008-0085-6
复制
发表时间：
2008-05
影响因子：
1.6
通讯作者：
R. Kwon;Georgios V. Dalakouras;Cheng Wang
中科院分区：
文献类型：
--
作者：
R. Kwon;Georgios V. Dalakouras;Cheng Wang
我们考虑了一种由已知的简单贪心方法得到的近似解的事后求值方法。我们推导出一个绩效界限，它是每件物品在子集上的最高平均奖励，以及分配的子集和基本物品的数量的函数。当解接近最优时，这个后验界可以揭示很多最优性。事后分析的优点之一是它不需要计算LP松弛的最优解。事后约束不能保证揭示所有问题实例的实质性最优性水平，但可以作为一种有用的工具，补充其他传统方法，用于集包装问题的事后评估。
We consider an approach for ex post evaluation of approximate solutions obtained by a well known simple greedy method for set packing. A performance bound is derived that is a function of the highest average reward per item over subsets as well as the number of allocated subsets and ground items. This a posterior bound can enable much revelation of optimality when the solution is near optimal. One of the advantages of the ex post analysis is that it does not require computing the optimal solution to the LP relaxation. The ex post bound will not be guaranteed to reveal substantial levels of optimality for all problem instances but can be a useful tool that is complementary to other traditional methods for ex post evaluation for the set packing problem.