Combinatorics Probability Computing · 1993 · 54 citations · 15 references
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationStochastic ProcessesApproximation AlgorithmsCombinatorial OptimizationConstrained OptimizationInteger ProgrammingProbabilistic CombinatoricsStochastic OptimizationEnumerative AlgorithmsExponential Time ComplexityKnapsack ApproximationKnapsack ProblemsRandomized Approximation AlgorithmsStochastic Combinatorial Optimization
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.
15