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 2031666601 1524700731
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. Abstract We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock problems by column generation, and may be used to separate cover inequalities with small support within cutting-plane approaches to integer linear programs. We focus our attention on approximation algorithms for the problem, describing a linear-storage Polynomial Time Approximation Scheme (PTAS) and a dynamic-programming based Fully Polynomial Time Approximation Scheme (FPTAS). The main ideas contained in our PTAS are used to derive PTAS's for the knapsack problem and its multi-dimensional generalization which improve on the previously proposed PTAS's. We finally illustrate better PTAS's and FPTAS's for the subset sum case of the problem in which profits and weights coincide. A fully polynomial time approximation scheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approaches need O(n+ 1 e 3 ) and O(n.1 e) space, respectively. Our new approximation scheme requires only O(n + 1 e 2 ) space while also reducing the running time.