A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions

Details A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions

2010-08-10

arxiv.org/abs/1008.1687v1

Computer Science

Data Structures and Algorithms

11 pages

Scientific paper

Given n elements with nonnegative integer weights w1,..., wn and an integer capacity C, 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 1+-eps in time polynomial in n and 1/eps (fully polynomial approximation scheme). More precisely, our algorithm takes time O(n^3 (1/eps) log (n/eps)). 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.

Affiliated with

Also associated with

No associations

Rating

A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583640