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

DOI10.1017/S0963548300000675MaRDI QIDQ4289294zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Dyer, Ajai Kapoor, Ljubomir Perković, Umesh V. Vazirani, Alan Frieze, R. Kannan

Publication date 28 April 1994

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300000675

zbMATH Keywords

Markov chainrandomized algorithmmultidimensional knapsack problem

Mathematics Subject Classification ID

Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Publication:4941826
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• An approximate dynamic programming approach to multidimensional knapsack problems
• A Fast Approximation Scheme for the Multiple Knapsack Problem
• An exact algorithm for large multiple knapsack problems
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• scientific article; zbMATH DE number 3993303
• Note—An Approximate Algorithm for Multidimensional Zero-One Knapsack Problems—A Parametric Approach
• An efficient algorithm for multi-dimensional nonlinear knapsack problems

Cites work

• A random polynomial-time algorithm for approximating the volume of convex bodies
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating the Permanent
• Probability Inequalities for Sums of Bounded Random Variables
• Random generation of combinatorial structures from a uniform distribution

Cited in

(12)

• Using stratified sampling to solve the Knapsack problem
• An exponential time 2-approximation algorithm for bandwidth
• Faster FPTASes for counting and random generation of knapsack solutions
• Learning fixed-dimension linear thresholds from fragmented data
• Approximately counting approximately-shortest paths in directed acyclic graphs
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• Discrete Optimal Transport with Independent Marginals is #P-Hard
• Gap filling as exact path length problem
• On approximating weighted sums with exponentially many terms
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
• A faster FPTAS for \#Knapsack

This page was built for publication: A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4289294)