A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
- 12 September 1993
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 2 (3) , 271-284
- https://doi.org/10.1017/s0963548300000675
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.Keywords
This publication has 1 reference indexed in Scilit:
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963