A Faster FPTAS for #Knapsack
From MaRDI portal
Publication:5002742
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
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
