Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs

Parikshit Gopalan, Adam R. Klivans, Raghu Meka

Type: Preprint

Publication Date: 2010-01-01

Citations: 3

DOI: https://doi.org/10.48550/arxiv.1008.3187

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs	2010	Parikshit Gopalan Adam R. Klivans Raghu Meka
+	An FPTAS for #Knapsack and Related Counting Problems	2011	Parikshit Gopalan Adam R. Klivans Raghu Meka Daniel tefankovic Santosh Vempala Eric Vigoda
+	A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions	2010	Daniel Štefankovič Santosh Vempala Eric Vigoda
+	A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions	2010	Daniel Štefankovič Santosh Vempala Eric Vigoda
+ PDF Chat	A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions	2012	Daniel Štefankovič Santosh Vempala Eric Vigoda
+ PDF Chat	Approximately Counting Knapsack Solutions in Subquadratic Time	2024	Weiming Feng Ce Jin
+ PDF Chat	Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically	2024	Moritz Buchem Paul Deuker Andreas Wiese
+	Fully polynomial time approximation schemes (FPTAS) for some counting problems	2016	Tzvi Alon
+ PDF Chat	Online Unbounded Knapsack	2024	Hans-Joachim Böckenhauer Matthias Gehnen Juraj Hromkovič Ralf Klasing Dennis Komm Henri Lotze Daniel Mock Peter Rossmanith M. Stocker
+	$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time	2023	Xiao Mao
+	Random walks in convex sets	2000	Benjamin Morris Alistair Sinclair
+ PDF Chat	Exact Counting and Sampling of Optima for the Knapsack Problem	2021	Jakob Bossek Aneta Neumann Frank Neumann
+ PDF Chat	A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant	2003	Mary Cryan Martin Dyer
+ PDF Chat	Approximately Counting Knapsack Solutions in Subquadratic Time	2025	Weiming Feng Ce Jin
+ PDF Chat	An empirical analysis of exact algorithms for the unbounded knapsack problem	2019	Henrique Becker Luciana S. Buriol
+	A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing	2010	Richard Beigel Bin Fu
+	A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing	2010	Richard Beigel Bin Fu
+	A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy	2016	Nir Halman
+	Combinatorial decomposition approaches for efficient counting and random generation FPTASes	2013	Roméo Rizzi Alexandru I. Tomescu
+	Branching proofs of infeasibility in low density subset sum problems	2008	Gábor Pataki Mustafa Kemal Tural

Works That Cite This (2)

Action	Title	Year	Authors
+ PDF Chat	An invariance principle for polytopes	2012	Prahladh Harsha Adam R. Klivans Raghu Meka
+ PDF Chat	A simple polynomial-time approximation algorithm for the total variation distance between two product distributions	2023	Weiming Feng Heng Guo Mark Jerrum Jiaheng Wang

Works Cited by This (8)

Action	Title	Year	Authors
+ PDF Chat	Simple deterministic approximation algorithms for counting matchings	2007	Mohsen Bayati David Gamarnik Dimitriy Katz Chandra Nair Prasad Tetali
+	Approximate counting by dynamic programming	2003	Martin Dyer
+	Counting independent sets up to the tree threshold	2006	Dror Weitz
+	Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions	2004	Ben Morris Alistair Sinclair
+ PDF Chat	Pseudorandom generators for polynomial threshold functions	2010	Raghu Meka David Zuckerman
+ PDF Chat	Fooling Functions of Halfspaces under Product Distributions	2010	Parikshit Gopalan Ryan O’Donnell Yi Wu David Zuckerman
+	A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries	2004	Mark Jerrum Alistair Sinclair Eric Vigoda
+	A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions	2010	Daniel Štefankovič Santosh Vempala Eric Vigoda