Abstract Given n independent integer-valued random variables X 1 , X 2 , … , X n and an integer C , we study the fundamental problem of computing the probability that the sum X = X 1 + X 2 + ⋯ + X n is at most C . We assume that each random variable X i is implicitly given by an oracle O i , which given two input integers n 1 , n 2 returns the probability of n 1 ≤ X i ≤ n 2 . We give the first deterministic fully polynomial-time approximation scheme (FPTAS) to estimate the probability up to a relative error of 1 ± ϵ . Our algorithm is based on the technique for approximately counting knapsack solutions, developed in (2011).
Our problem is a generalization of the counting knapsack problem. For the counting knapsack problem, Morris and Sinclair @cite_8 obtained the first FPRAS (fully polynomial-time randomized approximation scheme) based on the Markov Chain Monte-Carlo (MCMC) method. Dyer @cite_12 provided a completely different FPRAS based on dynamic programming. The first deterministic FPTAS is obtained by @cite_0 (see also the journal version @cite_13 ).
@cite_0 @cite_13 @cite_12 @cite_8
1989921461 1985985425 2003554015 2005107874
Given @math elements with non-negative integer weights @math and an integer capacity @math , we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most @math . We give the first deterministic, fully polynomial-time approximation scheme (FPTAS) for estimating the number of solutions to any knapsack constraint (our estimate has relative error @math ). Our algorithm is based on dynamic programming. Previously, randomized polynomial-time approximation schemes (FPRAS) were known first by Morris and Sinclair via Markov chain Monte Carlo techniques, and subsequently by Dyer via dynamic programming and rejection sampling. In addition, we present a new method for deterministic approximate counting using read-once branching programs. Our approach yields an FPTAS for several other counting problems, including counting solutions for the multidimensional knapsack problem with a constant number of constraints, the general integer knapsack problem, and the contingency tables problem with a constant number of rows. Given @math elements with nonnegative integer weights @math and an integer capacity @math , we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most the given capacity. We give a deterministic algorithm that estimates the number of solutions to within relative error @math in time polynomial in @math and @math (fully polynomial approximation scheme). More precisely, our algorithm takes time @math . Our algorithm is based on dynamic programming. Previously, randomized polynomial-time approximation schemes were known first by Morris and Sinclair via Markov chain Monte Carlo techniques and subsequently by Dyer via dynamic programming and rejection sampling. We give efficient algorithms to sample uniformly, and count approximately, the solutions to a zero-one knapsack problem. The algorithm is based on using dynamic programming to provide a deterministic relative approximation. Then "dart throwing" techniques are used to give arbitrary approximation ratios. We also indicate how further improvements can be obtained using randomized rounding. We extend the approach to several related problems: the m-constraint zero-one knapsack, the general integer knapsack (including its m-constraint version) and contingency tables with constantly many rows. We solve an open problem concerning the mixing time of symmetric random walk on the n-dimensional cube truncated by a hyperplane, showing that it is polynomial in n. As a consequence, we obtain a fully polynomial randomized approximation scheme for counting the feasible solutions of a 0-1 knapsack problem. The results extend to the case of any fixed number of hyperplanes. The key ingredient in our analysis is a combinatorial construction we call a "balanced almost uniform permutation," which is of independent interest.