A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
DOI10.1017/S0963548300000675zbMATH Open0819.90094DBLPjournals/cpc/DyerFKKPV93OpenAlexW2135756775WikidataQ56324083 ScholiaQ56324083MaRDI QIDQ4289294FDOQ4289294
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
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
Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Probability Inequalities for Sums of Bounded Random Variables
- Random generation of combinatorial structures from a uniform distribution
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Approximating the Permanent
Cited In (12)
- 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
- Using stratified sampling to solve the Knapsack problem
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)
