A Faster FPTAS for #Knapsack

DOI10.4230/LIPIcs.ICALP.2018.64zbMath1499.68405arXiv1802.05791OpenAlexW2963684650MaRDI QIDQ5002742

Paweł Gawrychowski, Oren Weimann, Liran Markin

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1802.05791

zbMATH Keywords

knapsackapproximate counting\(K\)-approximating sets and functions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

On computing probabilistic abductive explanations ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Probability estimation via policy restrictions, convexification, and approximate sampling ⋮ Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier

Cites Work

• Unnamed Item
• A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
• 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
• Counting independent sets up to the tree threshold
• A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
• Approximate counting by dynamic programming
• A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• Bounded Independence Fools Halfspaces
• Explicit construction of a small epsilon-net for linear threshold functions
• An FPTAS for #Knapsack and Related Counting Problems

This page was built for publication: A Faster FPTAS for #Knapsack