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

DOI10.1016/j.tcs.2016.06.015zbMath1348.68295OpenAlexW2424560073MaRDI QIDQ306252

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

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

Related Items (7)

Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ The TV advertisements scheduling problem ⋮ 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 ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier

Cites Work

• Unnamed Item
• Pseudorandom Generators for Polynomial Threshold Functions
• A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
• 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
• Approximate counting by dynamic programming
• Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
• An FPTAS for #Knapsack and Related Counting Problems

This page was built for publication: A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy