Faster FPTASes for Counting and Random Generation of Knapsack Solutions
Faster FPTASes for Counting and Random Generation of Knapsack Solutions
复制标题
用于计数和随机生成背包解决方案的更快 FPTAS
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Alexandru I. Tomescu
中科院分区：
文献类型：
--
作者：
Romeo Rizzi;Alexandru I. Tomescu
我们给出了更快，更简单的完全多项式时间近似计划（FPTASes）的P-完全问题计数0/1背包解决方案，并为它的随机生成对应。我们的方法是基于动态规划和离散化的大量通过浮点运算。我们改进了Gopalan等人，FOCS 2011），（Stefankovic等人，SIAM J. Comput. 2012）和（Dyer，STOC 2003）中的随机计数和随机生成算法。我们还改进了弧加权有向无环图中计数0/1背包解问题的复杂性。
We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for the #P-complete problem of counting 0/1 Knapsack solutions, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes in (Gopalan et al., FOCS 2011), (Stefankovic et al., SIAM J. Comput. 2012) and the randomized counting and random generation algorithms in (Dyer, STOC 2003). We also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.