A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy

DOI10.1016/J.TCS.2016.06.015MaRDI QIDQ306252zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dynamic programmingapproximate counting\(K\)-approximating sets and functionsbinding constraintsinteger knapsack

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 6861894
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• A faster FPTAS for \#Knapsack
• Approximate counting by dynamic programming
• Faster FPTASes for counting and random generation of knapsack solutions

Cites work

• scientific article; zbMATH DE number 19091 (Why is no real title available?)
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• A fully polynomial-time approximation scheme for single-item stochastic inventory control with discrete demand
• An FPTAS for #Knapsack and Related Counting Problems
• Approximate counting by dynamic programming
• Faster FPTASes for counting and random generation of knapsack solutions
• Fully polynomial time approximation schemes for stochastic dynamic programs

Cited in

(14)

• Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
• The TV advertisements scheduling problem
• scientific article; zbMATH DE number 7401920 (Why is no real title available?)
• A faster FPTAS for \#Knapsack
• Faster FPTASes for counting and random generation of knapsack solutions
• Strongly polynomial FPTASes for monotone dynamic programs
• scientific article; zbMATH DE number 6861894 (Why is no real title available?)
• Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• A faster FPTAS for counting two-rowed contingency tables
• Faster FPTASes for counting and random generation of knapsack solutions
• Approximate \#knapsack computations to count semi-fair allocations
• Approximate counting by dynamic programming
• Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states

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)