An FPTAS for #Knapsack and Related Counting Problems

DOI10.1109/FOCS.2011.32zbMath1292.68167OpenAlexW1989921461MaRDI QIDQ5495001

Daniel Štefanković, Raghu Meka, Eric Vigoda, Adam R. Klivans, Parikshit Gopalan, Santosh Vempala

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.32

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (21)

Completeness Results for Counting Problems with Easy Decision ⋮ A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Theoretical insights and algorithmic tools for decision diagram-based optimization ⋮ Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ Faster FPTASes for counting and random generation of knapsack solutions ⋮ On computing probabilistic abductive explanations ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ Computation of the random arrival rule for bankruptcy problems ⋮ Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States ⋮ A Faster FPTAS for #Knapsack ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ A fully polynomial-time approximation scheme for approximating a sum of random variables ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Estimating the probability of meeting a deadline in schedules and plans ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Probability estimation via policy restrictions, convexification, and approximate sampling ⋮ Approximately counting approximately-shortest paths in directed acyclic graphs

This page was built for publication: An FPTAS for #Knapsack and Related Counting Problems