Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
复制标题
使用分支程序的背包及相关计数问题的多项式时间逼近方案
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Raghu Meka
中科院分区：
文献类型：
--
作者：
Parikshit Gopalan;Adam R. Klivans;Raghu Meka
我们给出了一个确定性的多项式时间算法，用于近似计算背包问题任何实例的{0，1}-解的数量。在一个长度为n，总权重为W，精度参数为eps的实例上，我们的算法在时间上产生一个（1 + eps）-乘法逼近poly（n，log W，1/eps）。我们还给出了算法相同的保证一般整数背包，多维背包问题（具有恒定数量的约束）和列联表（具有恒定数量的行）。在此之前，只有随机近似计划已知的这些问题，由于工作的莫里斯和辛克莱和工作的戴尔。
我们的算法的工作原理是通过构建小宽度，只读一次的分支程序近似的基础解决方案空间下仔细选择的分布。作为这种方法的副产品，我们获得了新的查询算法的学习函数的k半空间关于均匀分布在{0，1}^n。我们的算法的运行时间是多项式的精度参数eps。以前，即使对于k=2的情况，也只知道对eps具有指数依赖性的算法。
We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms with identical guarantees for general integer knapsack, the multidimensional knapsack problem (with a constant number of constraints) and for contingency tables (with a constant number of rows). Previously, only randomized approximation schemes were known for these problems due to work by Morris and Sinclair and work by Dyer.
Our algorithms work by constructing small-width, read-once branching programs for approximating the underlying solution space under a carefully chosen distribution. As a byproduct of this approach, we obtain new query algorithms for learning functions of k halfspaces with respect to the uniform distribution on {0,1}^n. The running time of our algorithm is polynomial in the accuracy parameter eps. Previously even for the case of k=2, only algorithms with an exponential dependence on eps were known.