A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
DOI10.1016/J.TCS.2016.06.015zbMATH Open1348.68295OpenAlexW2424560073MaRDI QIDQ306252FDOQ306252
Authors: Nir Halman 
Publication date: 31 August 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.06.015
Recommendations
dynamic programmingapproximate counting\(K\)-approximating sets and functionsbinding constraintsinteger knapsack
Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Approximation algorithms (68W25)
Cites Work
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- An FPTAS for #Knapsack and Related Counting Problems
- Approximate counting by dynamic programming
- Pseudorandom generators for polynomial threshold functions
- Faster FPTASes for counting and random generation of knapsack solutions
- A fully polynomial-time approximation scheme for single-item stochastic inventory control with discrete demand
- Title not available (Why is that?)
- Fully polynomial time approximation schemes for stochastic dynamic programs
Cited In (14)
- Title not available (Why is that?)
- Faster FPTASes for counting and random generation of knapsack solutions
- A faster FPTAS for counting two-rowed contingency tables
- Approximate counting by dynamic programming
- The TV advertisements scheduling problem
- Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States
- Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- Title not available (Why is that?)
- Approximate \#knapsack computations to count semi-fair allocations
- Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
- Faster FPTASes for counting and random generation of knapsack solutions
- A faster FPTAS for \#Knapsack
- Strongly polynomial FPTASes for monotone dynamic programs
This page was built for publication: A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306252)
