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

DOI10.1017/S0963548300000675zbMath0819.90094OpenAlexW2135756775WikidataQ56324083 ScholiaQ56324083MaRDI QIDQ4289294

Ljubomir Perković, Ajai Kapoor, Martin Dyer, Umesh V. Vazirani, Ravindran Kannan, Alan M. Frieze

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

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

Related Items

On approximating weighted sums with exponentially many terms, An exponential time 2-approximation algorithm for bandwidth, Faster FPTASes for counting and random generation of knapsack solutions, Discrete Optimal Transport with Independent Marginals is #P-Hard, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, A Faster FPTAS for #Knapsack, Gap Filling as Exact Path Length Problem, Using stratified sampling to solve the Knapsack problem, Learning fixed-dimension linear thresholds from fragmented data, Approximately counting approximately-shortest paths in directed acyclic graphs

Cites Work

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