论文标题
预期性能和最坏情况的情况分析0-1背包问题的分界线和扭曲方法
Expected Performance and Worst Case Scenario Analysis of the Divide-and-Conquer Method for the 0-1 Knapsack Problem
论文作者
论文摘要
在本文中，我们提供了解决0-1背包问题的分隔和拼接方法的质量证书：最坏的情况和预期性能的估计。给出了概率设置，并定义了主要的随机变量，以分析预期性能。对于该方法的一次迭代，效率严格近似，这些值用于得出一般分裂和串联树的性能的分析估计。通过统计上适合的数值实验，对所有理论结果进行了验证，以更广泛地说明该方法。
In this paper we furnish quality certificates for the Divide-and-Conquer method solving the 0-1 Knapsack Problem: the worst case scenario and estimates for the expected performance. The probabilistic setting is given and the main random variables are defined for the analysis of the expected performance. The efficiency is rigorously approximated for one iteration of the method then, these values are used to derive analytic estimates for the performance of a general Divide-and-Conquer tree. All the theoretical results are verified with statistically suited numerical experiments for a wider illustration of the method.
