A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem

Martin Dyer, Alan Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perković, Umesh Vazirani

Combinatorics Probability Computing · 1993 · 54 citations · 15 references

Concepts

Abstract

We describe a time randomized algorithm that estimates the number of feasible solutions of a multidimensional knapsack problem within 1 ± ε of the exact number. (Here r is the number of constraints and n is the number of integer variables.) The algorithm uses a Markov chain to generate an almost uniform random solution to the problem.

References

15